Given an array of n integers equal to zero. There are 3 type of queries:
- Increase all elements from l to r by 1
- Decrease all elements from l to r by 1
- 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)
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)
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
Check the idea of Segment Tree Beats and maybe hopefully it'll help.
Could you please elaborate on how Segment Tree Beats could be used here? What would be the potential value?
Marinush
Like this problem: https://www.luogu.com.cn/problem/P5324
With some thinking, the problem comes to the given one by rakkoon. Here's the editorial: https://www.luogu.com.cn/problem/solution/P5324
Is there a problem link available for the problem?
Marinush
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
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?