We have array of zeros of length N. There are 3 types of queries in the problem:
- Add 1 to all nums with indexes in range [l, r].
- Subtract 1 from all nums with indexes in range [l, r].
- Print count of zeros in [l, r].
In each step there are no negative numbers.
I am solving it so: Make sqrt-decomposition, for each block store deque, where d[i] is count of i in the block. When we need to add 1 to all nums in the block, just push_front(0), it'll shift all the values by 1. Similarly pop_front(), when we subtracting 1 from all nums in the block. If block isn't fully in the range manually change counts. For 3rd query type summarise d[0] for blocks inside the range, for first&last blocks run cycle and count zeros. Complexity O(N√N)
Is this solution correct? Are there solutions faster?
This problem is actually a subproblem for the sweep line solution of the area of union of rectangles problem.
It can be solved rather straightforwardly with a segment tree with lazy propagation. For each node in the segment tree, simply maintain the minimum m as well as the number of occurrences c of the minimum. Since m is always nonnegative, we can simply check whether m is zero; if it is, the node contributes its c occurrences of zero, and otherwise, zero doesn't appear at all, so this node doesn't contribute anything.
You should be able to maintain these values without too much difficulty if you are familiar with segment trees already.
Thanks, i didn't know such interesting solution.
rajat1603 sampriti
Normal Friends : * Tags on Facebook *
Coder Friends : * Tags on Codeforces blog entries *
Haha, this is an inside joke. It would be impossible to find this specific question on any Facebook page.
Only Legends use Codeforces messaging.
I guess they don't use it.