Editorial for RGPC '18 P4 - Higgs


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: RuAr

Since we have to check which ticks are prime, we can use the Sieve of Eratosthenes to generate a list of primes. We then have to perform interwoven updates and queries, meaning that both operations must be efficient. Using traditional data structures, we can only achieve imbalanced \mathcal{O}(1) and \mathcal{O}(N) operations (with prefix sum/difference arrays), or \mathcal{O}(\log N) and \mathcal{O}(N \log N) operations (with Binary Indexed Trees or BITs). We thus have to use a range update and range query binary indexed tree that would enable \mathcal{O}(\log N) for both operation types.

We notice that, given a single range update of [a, b] by k, and then a query to the sum S_x of elements in the range [0, x], there are 3 possibilities for the value of the sum:

\displaystyle S_x =
\begin{cases}
    0 & \text{if } x < a \\
    k(x - (a-1)) = kx - k(a-1) & \text{if } a \leq x \leq b \\
    k(b - (a-1)) = kb - k(a-1) & \text{if } x > b
\end{cases}

We see that we can express this sum in the form \delta x - \lambda, where \delta is the value in the array at index x after update, and \lambda is a "fix" value that we subtract in order to correct the sum. The value of \lambda varies depending on x (draw it out for better understanding):

\displaystyle \lambda =
\begin{cases}
    0 & \text{if } x < a \\
    k(a-1) & \text{if } a \leq x \leq b \\
    -kb + k(a-1) & \text{if } x > b
\end{cases}

Showing that this idea generalizes to multiple updates and queries is left as an exercise for the reader. With this mathematical formulation, we can use 2 BITs to implement this algorithm: one to store the accumulated \delta values (which we maintain like a normal range update point query BIT), and one to store the accumulated \lambda corrections.

Or, you know, use a segment tree with lazy propagation, but the BIT solution is less clunky.

Time complexity: \mathcal{O}(T(\log \log T + \log N))


Comments

There are no comments at the moment.