### rakkoon69's blog

By rakkoon69, history, 17 months ago,

Given an array of n integers equal to zero. There are 3 type of queries:

1. Increase all elements from l to r by 1
2. Decrease all elements from l to r by 1
3. Count the number of zeros from l to r

Is there an efficient way to solve this problem in O(N log N), O(N sqrt(N)) or at least O(N log2 N)? Thank you in advance!

I've found a O(N log N) solution which I've implemented in 258E - Little Elephant and Tree, my submission: 226468052 (The STree namespace)

• +16

| Write comment?
 » 17 months ago, # | ← Rev. 2 →   0 You could do this with segment tree with lazy propagation, I believe? (https://cp-algorithms.com/data_structures/segment_tree.html#range-updates-lazy-propagation)
•  » » 17 months ago, # ^ |   0 Can u show me how? Cause it seems impossible to do so, the increasing and decreasing queries work perfectly well with lazy propagation but I have no good idea for the last type of query
•  » » » 17 months ago, # ^ | ← Rev. 3 →   +7 Check the idea of Segment Tree Beats and maybe hopefully it'll help.
•  » » » » 17 months ago, # ^ |   -6 Could you please elaborate on how Segment Tree Beats could be used here? What would be the potential value?Marinush
•  » » » » » 17 months ago, # ^ |   +6 Like this problem: https://www.luogu.com.cn/problem/P5324With some thinking, the problem comes to the given one by rakkoon. Here's the editorial: https://www.luogu.com.cn/problem/solution/P5324
 » 17 months ago, # |   0 Is there a problem link available for the problem?Marinush
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 I think I have a solution in NsqrtN. Split the array into Sqrt(N) blocks. Now, every add/subtract query we do will go through at most sqrt(N) complete blocks and 2 non-complete blocks. For each block we store a frequency array of elements, we know the elements won't exceed Q in absolute values (Q is the number of modifications). Now for updates: For each complete block, just add 1/-1 to the block depending on the query. For noncomplete blocks change the frequency of the previous a[i] to the new a[i] that is obtained by performing the addition/subtraction.Now for queries: For each complete block, we add to the answer the frequency of -sum_of_block. For noncomplete we just check if its value + sum_of_block is 0 or not and add 1 to the answer for the query if it is.Marinush
•  » » » 17 months ago, # ^ |   +3 Actually, I came up with this problem while solving Mars Maps (BOI 2001). And thank you for your answer! And do you have any solution using segment tree?
•  » » » » 17 months ago, # ^ |   +7 const int N=150000*3+10; #define mid ((l+r)>>1) #define ls (x<<1) #define rs (x<<1|1) int n,m; struct node{ int mi,cnt; int ans,ad; }t[4*N]; int a[N],buc[N]; int st,lim; void pushup(int x){ t[x].mi=min(t[ls].mi,t[rs].mi); t[x].cnt=(t[ls].mi==t[x].mi?t[ls].cnt:0)+(t[rs].mi==t[x].mi?t[rs].cnt:0); t[x].ans=t[ls].ans+t[rs].ans; } void tag(int x,int c){ t[x].mi+=c; t[x].ans=(t[x].mi==0)?t[x].cnt:0; t[x].ad+=c; } void pushdown(int x){ if(t[x].ad){ tag(ls,t[x].ad);tag(rs,t[x].ad); t[x].ad=0; } } void build(int x,int l,int r){ if(l==r){ t[x].cnt=1;t[x].ans=1; return; } build(ls,l,mid); build(rs,mid+1,r); pushup(x); } void upda(int x,int l,int r,int L,int R,int c){ if(L<=l&&r<=R){ tag(x,c);return; } pushdown(x); if(L<=mid) upda(ls,l,mid,L,R,c); if(mid0); upda(1,1,lim,k,k,c); buc[x]+=c; }