All submissions for this problem are available.
Given a binary represantation of number N. You are to find how many numbers from 0 to N have even number of ones in their binary represantation.
There is also an update operation, update (L,R), which means that all bits of N from Lth to Rth are flipped, i.e. ones to zeroes and vice versa. You have to also find the answer after each of these updates.
The first line of input file contains binary represantation of number N. The second line contains number M - the number of update queries. Then M lines follow that describe each update query by two numbers - L and R. Note that the digits of N are numbered from left to right. That is, the leftmost(most significant) bit is numbered 1.
Output the answer for initial value of N and also after each of the M updates modulo 109+7 in separate lines.
- 1 ≤ L ≤ R ≤ number of bits in N ≤ 106
- 1 ≤ M ≤ 105
- all digits of N are either '0' or '1'.
Input: 000 5 3 3 2 3 3 3 2 3 1 3 Output: 1 1 1 2 1 4
After the final operation, N becomes 7. All numbers in range [0..7] that have even number of ones in their binary representation are: 0, 3, 5 and 6.
|Tags||Rubanenko, cook38, medium, segment-trees|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.