Editorial for Bubble Cup V9 G Heroes of Making Magic III

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.

For queries of type 2, we are only interested in the elements $A_k$ $A_{k}$ with $n$ $n$ in the interval $[i, j]$ $[i, j]$ , and nothing else. For the sake of convenience, label those elements as $a_0, a_1, \dots, a_n$ $a_{0}, a_{1}, \dots, a_{n}$ , where $n = j-i+1$ $n = j - i + 1$ .

It can be easily seen that in order to clear a segment, we can just move back and forth between positions $0$ $0$ and $1$ $1$ until $a_0$ $a_{0}$ becomes $0$ $0$ , move to $1$ $1$ and alternate between $1$ $1$ and $2$ $2$ , etc – until we zero out the last element. If we want this procedure to succeed, several (in)equalities must hold:

$a_0 \ge 1$ $a_{0} \geq 1$ (since we have to decrease the first element of the segment in the first step)
$a_1-a_0 \ge 0$ $a_{1} - a_{0} \geq 0$ (after following this procedure, $a_1$ $a_{1}$ is decreased exactly by $a_0$ $a_{0}$ , and we end up on $a_1$ $a_{1}$ )
$a_2-(a_1-a_0+1) = a_2-a_1+a_0-1 \ge 0$ $a_{2} - (a_{1} - a_{0} + 1) = a_{2} - a_{1} + a_{0} - 1 \geq 0$ , or, $a_2-a_1+a_0 \ge 1$ $a_{2} - a_{1} + a_{0} \geq 1$
$a_3-a_2+a_1-a_0 \ge 0$ $a_{3} - a_{2} + a_{1} - a_{0} \geq 0$ , …
In general, $a_m-a_{m-1}+a_{m-2}-\dots+(-1)^m a_0$ $a_{m} - a_{m - 1} + a_{m - 2} - \dots + (- 1)^{m} a_{0}$ has to be greater or equal to $0$ $0$ , if $m$ $m$ is odd, and $1$ $1$ , if $m$ $m$ is even

Equivalently, if we define a new sequence $d'$ $d^{'}$ , such that $d'_0 = a_0$ $d_{0}^{'} = a_{0}$ , and $d'_m = a_m-d'_{m-1}$ $d_{m}^{'} = a_{m} - d_{m - 1}^{'}$ , these inequalities are equivalent to stating that $d'_0, d'_2, d'_4, \dots \ge 1$ $d_{0}^{'}, d_{2}^{'}, d_{4}^{'}, \dots \geq 1$ and $d'_1, d'_3, d'_5, \dots \ge 0$ $d_{1}^{'}, d_{3}^{'}, d_{5}^{'}, \dots \geq 0$ .

Of course, we do not have to store the $d$ $d$ array for each pair of indices $i, j$ $i, j$ , but it is enough to calculate it once, for the entire initial array $A$ $A$ . Then, we can calculate the appropriate values of $d'_k$ $d_{k}^{'}$ for any interval $[i, j]$ $[i, j]$ ( $k$ $k$ is the zero-based relative position of an element inside the segment): Let $c = d_{i-1}$ $c = d_{i - 1}$ . Then,

For even values of $k$ $k$ , $d'_k = c+d_{i+k}$ $d_{k}^{'} = c + d_{i + k}$
For odd values of $k$ $k$ , $d'_k = d_{i+k}-c$ $d_{k}^{'} = d_{i + k} - c$

Now we only need a way to maintain the array $d$ $d$ after updates of the form " $1\ i\ j\ v$ $1 i j v$ ". Fortunately, we can see that this array is updated in a very regular way:

Elements on even positions inside the interval $[i, j]$ $[i, j]$ are increased by $v$ $v$
If $j-i$ $j - i$ is even, elements on positions $j+1, j+3, j+5, \dots$ $j + 1, j + 3, j + 5, \dots$ are decreased by $v$ $v$ , and elements on positions $j+2, j+4, j+6, \dots$ $j + 2, j + 4, j + 6, \dots$ are increased by $v$ $v$

All of this can be derived from our definition of $d$ $d$ .

Both of these queries can be efficiently implemented using a lazy-propagation segment tree, where each internal node stores two numbers, the minimal of its odd- and even-indexed leaves.

Using the approach described above, we arrive at a solution with the complexity of $\mathcal O(q \log n)$ $O (q \log n)$ .

Comments

There are no comments at the moment.