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
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)
I see tag this problem — sqrt decomposition. task
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.
I have no idea this problem. Tell me your idea. test 2 sub 1 add 5
Your test is incorrect:
"It is guaranteed that at any time the number P can not be negative."
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
code with some explanation:
ideone
hou hou da vi iz anglii
thanks very much!!!
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....
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?
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.
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.