## Editorial for DMOPC '19 Contest 6 P3 - Grade 11 Math

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

For the first subtask, it suffices to process each query by simply iterating from to , and adding to the answer when a bit that was not previously set is set. As well, no calculations involving modulo are required as the answer is at most .

**Time complexity:**

For the full marks, observe that each bit in the string is set at most once. One way to take advantage of this is to use a set data structure such as `std::set`

in C++ or `TreeSet`

in Java to maintain the set of indices which have not been set yet. In doing this, each bit is removed from the set at most once, until the set is empty and all bits have been set. Then, for each query, search for the first element which is greater than , and continue to set all bits coming after it in the set that fall within the range . Alternatively, disjoint-set union structures such as path compression can also be used to process queries efficiently. Note that it is required to provide the answer modulo , using the multiplicative and additive properties of modular arithmetic.

**Pseudocode (set solution)**

```
MODULO=1e9+7
function add(a, b)
return (a + b) mod MODULO
read |S|, M, S
unset = [0, |S|)
answer = 0
(pre-process powers of 2)
powers = [1]
for i in (0, M)
powers[i] = add(powers[i-1], powers[i-1])
reverse powers
do M times
read l, r
x is smallest number in unset >= l
while x <= r
ans = add(ans, powers[x])
remove x from unset
x is smallest number in unset >= l
print ans
```

**Time complexity:** or

## Comments

:tzak: