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 \ge 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 \ge 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 \ge 0~, or, $a_2-a_1+a_0 \ge 1$ ~a_2-a_1+a_0 \ge 1~
$a_3-a_2+a_1-a_0 \ge 0$ ~a_3-a_2+a_1-a_0 \ge 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 \ge 1~ and $d'_1, d'_3, d'_5, \dots \ge 0$ ~d'_1, d'_3, d'_5, \dots \ge 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)$ ~\mathcal O(q \log n)~.

Comments

There are no comments at the moment.