puf's blog

Problem on queries
By puf, history, 7 years 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?

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

»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, i didn't know such interesting solution.

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

rajat1603 sampriti

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Normal Friends : * Tags on Facebook *

    Coder Friends : * Tags on Codeforces blog entries *

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Haha, this is an inside joke. It would be impossible to find this specific question on any Facebook page.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      Only Legends use Codeforces messaging.

      → Reply