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?
