- Time limit: 1.50 s
- Memory limit: 512 MB
Same as A21 but harder!
If the last test crashes, make sure you are using at most ~2m bits of memory.
The input is a binary data stream either from file or standard input.
The file contains the 64-bit integers:
- n - number of insertions and queries.
- m - number of bits to allocate for the bit array.
- n values to set.
- n values for sum queries.
For each value i, output the number of 1-bits in the first i bits of the Bit Array.
- m is less than or equal to 10^9.
- n is less than 10^7
As 64-bit binary:
4 10 2 4 6 8 3 4 5 6
1 1 2 2