puf's blog

By puf, history, 7 months ago, translation, In English,

We have array of zeros of length N. There are 3 types of queries in the problem:

  1. Add 1 to all nums with indexes in range [l, r].
  2. Subtract 1 from all nums with indexes in range [l, r].
  3. 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?

Read more »

  • Vote: I like it  
  • +3
  • Vote: I do not like it