Official

C - ARC Wrecker 2 Editorial by evima


We will show that the objective for the segment \([l, r]\) is achievable if and only if the following condition holds:

Condition 1: \(A_l + A_{l+2} + A_{l+4} + \cdots = A_{l+1} + A_{l+3} + A_{l+5} + \cdots\).

First, CoCondition 1 1 is necessary because the operation does not change the difference \((A_l + A_{l+2} + A_{l+4} + \cdots) - (A_{l+1} + A_{l+3} + A_{l+5} + \cdots)\).

(Illustration of the operation)

(The sentence at the top right says “No matter what we do, the difference doesn’t change,” and “奇数” and “偶数” means odd numbers and even numbers (positions).)

To show the sufficiency of Condition 1, note that we can ignore the following restriction of the second operation without affecting the achievability of the objective.

This operation can only be done when both of those buildings have heights of 1 or greater.

This is because if there is a sequence of operations that achieves the objective but violates this restriction, we can make it obey the restriction by changing the order of the operations so that all “increase” operations happen before all “decrease” operations.

Ignoring this restriction, we can successively make the heights of the buildings \(0\) from left to right. When we have made the heights of Buildings \(l, l+1, \cdots, r-1\) all zero, the height of Building \(r\) will be \(A_r - A_{r-1} + A_{r-2} - A_{r-3} + \cdots\), which is also \(0\) when Condition 1 holds.

(Illustration of the strategy)

(The sentence at the top-left says “Doing operations from left to right…”, the one at the top-right says “1 - 3 + 1 - 2 + 3 = 0 so we can make the heights all zero!”, and “ビル 1・2 に操作を行った” means “done operations on Buildings 1, 2.”)

Now that we have proven that the answer is the number of pairs \((l, r)\) satisfying Condition 1, let us rephrase it into the following:

Condition 2: Define a sequence \(B = (B_1, B_2, \cdots, B_N)\) as follows:

  • \(B_i = A_i\) if \(i\) is odd;
  • \(B_i = -A_i\) if \(i\) is even.

Then, \(B_l + B_{l+1} + \cdots + B_r = 0\) holds.

Furthermore, let us rephrase it again into the following:

Condition 3: Define a sequence \(C\) by \(C_i = B_1 + B_2 + \cdots + B_i\). Then, \(C_r - C_{l-1} = 0\) holds.

Now, the problem simply asks us to count pairs \((i, j)\) \([0 \leq i < j \leq N]\) such that \(C_i = C_j\). We can solve it using an associative array such as std::map, or using sorting to “compress” the values.

(Sample Implementations)

posted:
last update: