feruz.atamuradov's blog

By feruz.atamuradov, history, 7 years ago, translation, In English

Hi CF! I find problem sqrt decomposition. Sorry my english isn't well.

Roma and Vitala came up with the following game: add and subtract from the number of power two, and after each operation count the number of units in the binary number of this number. Who is faster and more correct, he won.

You have to help them: write a program with which they could check their calculations. The rules of the game are:

At the beginning of the game, the number P is zero. For the entire game, N operations are performed. Each operation is the addition to the number P or subtraction from the number P of the number 2S. After performing each operation, it is necessary to output the number of units in the binary representation of P. It is guaranteed that at any time the number P can not be negative.


Input

The first line of the input file INPUT.TXT contains an integer N (1 ≤ N ≤ 105) — the number of operations. The following N lines specify operations where each operation is specified by one of two lines: "add S" or "sub S", where S (0 ≤ S ≤ 105) is an integer.

The "add S" operation means that 2 S must be added to the P number.

The operation "sub S" means that the number P should subtract 2 S.


Output

For each of the N requests to the output file OUTPUT.TXT on a separate line, output the number of units in the binary record of the number P after performing this operation.

test

4 add 2 add 8 sub 3 sub 0 output: 1 2 6 7

  • Vote: I like it
  • -16
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
Rev. 4   Vote: I like it +15 Vote: I do not like it

Nice change constrains...

// don't look previous rev, it was written for N <  = 105, |S| <  = 105.

I can solve this problem when N <  = 105, |S| <  = 105 using segment tree.

O(NlogN)

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

    I see tag this problem — sqrt decomposition. task

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

      If you know how to find k-th one/zero and assign value on the interval, using sqrt decomposition, it must be easy problem for you.

      I don't know how to find k-th one/zero on the interval using sqrt decomposition, but I know how to do this using segment tree.

      I can explain how to solve this problem using segment tree. Then if you know how to find k-th one on the interval using sqrt decomposition, you can remake my solution using sqrt decomposition.

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

        I have no idea this problem. Tell me your idea. test 2 sub 1 add 5

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

          Your test is incorrect:

          "It is guaranteed that at any time the number P can not be negative."

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 8   Vote: I like it +9 Vote: I do not like it

        Ok, I try to explain :)

        If you understand my submission using set, it's easy to understand this solution:

        First of all, note that all the time we have an array with values 0-1 ( binary representation of a number ).

        Let M = 3 * 105.

        What changes when we add some value to the P ?

        for example:

        P=0

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 0 0 0 0 0

        add 4

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 0 1 0 0 0

        okay, what if something was on position 4?

        P=16

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 0 1 0 0 0

        add 4

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 0 0 1 0 0

        another example:

        P=184

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 1 1 1 0 1

        add 3

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 0 0 0 1 1

        Note, that we should find first zero on interval x .. M.

        It is easy to do using segment tree.

        Let this position U.

        We have to assign 0 on interval x..U-1 and assign 1 in position U.

        We can do this using segment tree with lazy propagation.

        // Okay, I believe this part is understandable.

        What changes if we subtract some value from P?

        for example:

        P=24

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 1 1 0 0 0

        sub 0

        P=23

        indices: 0 1 2 3 4 5 6 7

        array...: 1 1 1 0 1 0 0 0

        another exaple:

        P=48

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 0 1 1 0 0

        sub 3

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 1 0 1 0 0

        and last one

        P=12

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 1 1 0 0 0 0

        sub 2

        indices: 0 1 2 3 4 5 6 7

        array...: 0 0 0 1 0 0 0 0

        Note, that we should find first one on interval x .. M.

        It is also easy to do using segment tree :)

        Let this position U.

        We have to assign 1 on interval x..U-1 and assing 0 in position U.

        We also can do this using segment tree with lazy propagation.

        So the answer for each of the N requests will be sum on interval 0..M

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

        I don't know how to find k-th one/zero on the interval using sqrt decomposition, but I know how to do this using segment tree.

        that's why you are blue, man....

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 3   Vote: I like it +8 Vote: I do not like it

          I think it's little easier to do using segment tree instead of sqrt decomposition. Also segment tree works faster than sqrt :|

          Why I must know how to do this with sqrt decomposition when I know how to do this using segment tree?

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

            Because then you understand better how to think/code about sqrt decomposition and on problems where you can't use a standard tree you can use sqrt.

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

Guy, no offense , but knowing sqrt decomposition won't help you become Green(if improving is your goal keep reading further, otherwise just pass ).

Here's why: due to the fact that problems on CF that require knowing SQRT decomp. to solve them are E+...

If you can't solve A, B, C, D div.2 then you have other issues with your approach in learning.