DRGNDEN - Editorial

That finds the optimal previous of each point using a stack. I coded it that way so that I didn’t have to copy paste when building the forwards-tree and the backwards-tree.

Sounds like a kind of square root decomposition? Sounds right to me, I know a few others that tried that approach too

It’s a bit tight for the time limit but I think it’s viable with sufficiently small constant factor (as you’ve shown).

Great Editorial! If anyone knows some similar problems from CC, CF,SPOJ, please attach them in this thread. It would be helpful for everyone. Thanks! :slight_smile:

1 Like

Yes lets call it a decomposition maybe
With constant of >=600 it would cause tle

Input
Output

1 Like
#include <bits/stdc++.h>
using namespace std;

long long bss(vector<long long> &v,long long val){
    long long l=0,r = v.size()-1;
    while(l<=r){
        long long mid = (l+r)/2;
        if(v[mid]==val)return mid;
        else if(v[mid] < val)l = mid+1;
        else r = mid-1;
    }
    return -1;
}
// code for FenwickTree is taken from cp-algorithms.com
struct FenwickTree {
    vector<long long> bit;
    long long n;
    
    FenwickTree(long long n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<long long> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }
    long long sum(long long r) {
        long long ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    long long sum(long long l, long long r) {
        return sum(r) - sum(l - 1);
    }

    void add(long long idx, long long delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

struct Node{
    vector<long long> dd;
    vector<long long> ddv;
    FenwickTree pref;
};

struct segment_tree{
    vector<long long> h,a;
    long long qr,last,N;
    bool isposs;
    vector<Node> T;
    
    segment_tree(long long n){
        N = n;
        h.reserve(n+1);
        a.reserve(n+1);
        T.reserve(4*n+1);
    }
    
    void build(long long v,long long tl,long long tr){
        if(tl!=tr){
            long long tm = (tl+tr)/2;
            build(2*v,tl,tm);
            build(2*v+1,tm+1,tr);
        }
        T[v].dd.push_back(tl);
        for(long long i=tl+1;i<=tr;i++){
            if(h[i] > h[T[v].dd.back()])T[v].dd.push_back(i);
        }
        vector<long long> temp;
        for(auto i : T[v].dd){
            T[v].ddv.push_back(h[i]);
            temp.push_back(a[i]);
        }
        T[v].pref = FenwickTree(temp);
    }
    
    void update(long long v,long long tl,long long tr,long long pos,long long change){
        
        if(tl!=tr){
            long long tm = (tl + tr) / 2;
            if (pos <= tm)
                update(v*2, tl, tm, pos,change);
            else
                update(v*2+1, tm+1, tr, pos,change);
        }
            
        long long ind = bss(T[v].dd,pos);
        if(ind!=-1)T[v].pref.add(ind,change);
    }
    
    long long queryHelper(long long v,long long tl,long long tr,long long l,long long r){
        if(l > r) return 0;
        if (l == tl && r == tr) {
            auto it = upper_bound(T[v].ddv.begin(),T[v].ddv.end(),last);
            long long ind = it-T[v].ddv.begin();
            if(r==qr){
                if(it==T[v].ddv.end() || T[v].dd.back()!=qr){
                    isposs = false;
                    return -1;
                }
                else{
                    last = T[v].ddv.back();
                    return T[v].pref.sum(ind,T[v].ddv.size()-1);
                }
            }
            else{
                if(it!=T[v].ddv.end()){
                    last = T[v].ddv.back();
                    return T[v].pref.sum(ind,T[v].ddv.size()-1);
                }
                else{
                    return 0;
                }
            }
        }
        long long tm = (tl + tr) / 2;
        return queryHelper(v*2, tl, tm, l, min(r, tm)) + queryHelper(v*2+1, tm+1, tr, max(l, tm+1), r);
    }
    
    long long query(long long l,long long r){
        qr = r;
        isposs = true;
        last = -1;
        long long ans = queryHelper(1,1,N,l,r);
        if(isposs)return ans;
        else return -1;
    }
};

int main() {
    
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    long long n,q;
	cin >> n >> q;
	
	segment_tree Front(n),Back(n);
	for(long long i=1;i<=n;i++){
	    cin >> Back.h[i];
	    Front.h[n-i+1] = Back.h[i];
	}
	for(long long i=1;i<=n;i++){
	    cin >> Back.a[i];
	    Front.a[n-i+1] = Back.a[i];
	}
	
	Front.build(1,1,n);
	Back.build(1,1,n);
	
	while(q--){
	    long long type,s,e;
	    cin >> type >> s >> e;
	    if(type==1){
	        Back.update(1,1,n,s,e - Back.a[s]);
	        Back.a[s] = e;
	        
	        Front.update(1,1,n,n-s+1,e - Front.a[n-s+1]);
	        Front.a[n-s+1] = e;
	    }
	    else cout << ( s < e ? Front.query(n-e+1,n-s+1) : Back.query(e,s) ) << '\n';
	}
}

QTREE and Anudeep2011’s blog

The blog has a huge list of HLD problems :slight_smile:

4 Likes

Wouldn’t a point update change the structure of our whole flattened tree? How is update to two nodes of segment tree going to help?

Test
25 20

3 1 1 2 3 1 4 4 4 3 6 4 5 2 1 4 4 5 1 1 1 1 2 4 5

1 2 1 2 1 2 1 3 1 2 2 1 1 2 2 2 1 2 1 2 1 2 1 3 1

2 23 9

2 2 3

2 2 4

2 23 9

2 2 6

2 2 4

2 23 9

2 7 3

1 12 6

2 1 4

2 23 9

2 2 7

2 22 25

1 6 2

2 23 9

2 11 3

2 2 20

2 25 24

2 8 3

2 2 7

Ans:
-1

-1

-1

-1

-1

-1

-1

5

3

-1

-1

-1

-1

7

-1

4

-1

-1

The structure of the tree is dependent only on the heights. The structure of the tree itself never changes.

What we are updating is the values on each node

1 Like

I had the same idea of having one segment tree for max height and other two for left and right direction. But i got stuck in the merging part in segment tree, where i needed to find closest point with height strictly greater than the highest point of the other part.

My solution is the same as in the editorial, but note that you do not need any kind of heavy light decomposition (I did not use it). When using a queue to assign the rightmost hill to the left which is > in height for each hill, use 4 queues instead. So for each assign rightmost hill to the left which is >, ‘’ ‘’ ‘’ which is >= and the mirror. Now you can use two segment trees to get your job done and use the >= one for checking purposes if a path exists.

1 Like

Can u tell me why this was giving TLE ?
https://www.codechef.com/viewsolution/35538520

Hi Varun,
You could find the closest point to the left or right with height strictly greater height using Stacks.

Here, do refer this : Find the nearest smaller numbers on left side in an array - GeeksforGeeks

Also, you can try to solve : Problem - C2 - Codeforces

1 Like

The TL of 1 sec was brutal for me. I had to optimize my HLD code a lot because of the constant factors (and also I’m sure there is a lot of other redundant stuff because this was my first time trying HLD).

But I think the test cases are weak in subtask 3. Very weirdly my submission using the normal HLD code gave AC in subtask 1 and 3 but TLE in subtask 2.

Which makes no sense because the test cases of ST#2 should be a subset of ST#3. But who am I to argue when I can benefit from this XD

So I just copied the code I had submitted before for partial points of ST#2, called it void scam() (a fitting name), and put it in my HLD submission. If a test case didn’t have a query of type 1 within the first 1000 queries(a random heuristic) I would identify it as a test case from ST#2 and call void scam()

Surprisingly it works XD
Here is the first code
Here is the “improved one”

1 Like

It is working on this test case.

I tried same approach but instead of array I used set which store elements of a block only from current max till max of next block means storing only the path. But it is not working on test cases other than sample. Can you check my solution. here is link given

Good catch. Since there was an \mathcal{O}(\log n)-per-query solution (tree flattening instead of HLD) I was maybe more lax than I should have been with the strength of the test cases discriminating between the \mathcal{O}(\log^2 n) test cases. Oh well, bringing the constant factor down isn’t too bad anyway :))

1 Like
#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<string>
#define si(x) scanf("%d",&x);
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<ll>
#define ll long long int
#define mod 1000000007
#define ld long double
#define llu unsigned long long int
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define tezz ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define f(i,n) for(int i=0;i<n;i++)
#define f1(i,j,n) for(int i=j;i<n;i++)
#define INF 1000000000
#define pll pair<ll,ll>
using namespace std;//fuck copying and ratings
int main(){   
    tezz;
	int t=1;
	//cin>>t;
	while(t--){
		ll n,q;
		cin>>n>>q;
		
		ll h[n+1]={0},a[n+1]={0};

		f1(i,1,n+1)
			cin>>h[i];
		f1(i,1,n+1)
			cin>>a[i];
		while(q--){
			ll o,b,c;
			cin>>o>>b>>c;
			if(o==1){
				ll k=c;
				a[b]=k;
			}
			else if(o==2){
				if(b>c){
					ll flag=0,diff=0;
					vll v1;
					for(int i=b-1;i>c;i--){
						if(h[i]<=h[b] and h[i]>=h[c]){
							v1.pb(i);
						}
						if(h[i]>=h[b])
							flag=-1;
					}
					ll sum=0;
					f(i,v1.size())
						sum+=a[v1[i]];
					sum+=(a[b]+a[c]);
					if(v1.size()){
						f(i,v1.size()-1){
							if(h[v1[i]]<h[v1[i+1]]){
								diff+=a[v1[i]];
							}
						}	
					}
					else{
						if(h[c]<h[b])	
							sum=a[b]+a[c];
						else
							sum=-1;
					}
					if(flag!=-1)
						cout<<sum-diff<<endl;
					else
						cout<<-1<<endl;
				}
				else if(b<c){
					ll flag=0,diff=0;
					vll v2;
					for(int i=b+1;i<c;i++){
						if(h[i]<=h[b] and h[i]>=h[c]){
							v2.pb(i);
						//		cout<<i<<" ";
						}
						if(h[i]>=h[b] )
							flag=-1;
					}
					//cout<<endl;
					ll sum=0;
					f(i,v2.size()){
						sum+=a[v2[i]];
					}
					sum+=(a[b]+a[c]);
					if(v2.size()){
						f(i,v2.size()-1){
							if(h[v2[i]]>h[v2[i+1]])
								diff+=a[v2[i]];
						}
					}
					else{
						if(h[c]<h[b])
							sum=(a[b]+a[c]);
						else
							sum=-1;
					}
					if(flag!=-1)
						cout<<sum-diff<<endl;
					else
						cout<<-1<<endl;
				}
				else{
					cout<<-1<<endl;
				}
				
			}
		}
	
	}
    return 0;
}

I tried a brute force approach for 10 pts but its failing though I see many wrote a similar solution which is given 10 pts,can you please help me where I am getting it wrong.

Can somebody explain why this soln using set is wrong for the first subtask
Submission link (CodeChef: Practical coding for everyone)