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

Remember to use this editorial 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: Tzak

For the first subtask, it suffices to process each query by simply iterating from l to r, 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 2^0+2^1+2^2+\cdots+2^{20}=2^{21}-1<10^9+7.

Time complexity: \mathcal O(|S| \cdot M)

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 l, and continue to set all bits coming after it in the set that fall within the range [l,r]. 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 10^9+7, 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: \mathcal O(M+|S| \log |S|) or \mathcal O(|S|+\alpha(|S|) M)

Comments


  • 11
    Aaeria  commented on June 24, 2020, 11:08 p.m.

    tzak


  • 2
    kdrkdr  commented on June 24, 2020, 6:45 p.m. ← edited

    :tzak: