2227G: Drowning

Observation 1: two invariants smack you in the face

Take the alternating sum of an array: $A(c)=c_1-c_2+c_3-c_4+\dots$

If we reduce a triplet $(c_{i-1},c_i,c_{i+1}) \to x=c_{i-1}-c_i+c_{i+1},$ then inside the global alternating sum, those three terms had signs $+,-,+$ or $-,+,-$ , and they get replaced by exactly the same signed contribution. So the alternating sum is preserved.

Also, each move decreases the length by $2$ , so the parity of the length is preserved.

That already gives a necessary condition:

to end at a single element, the length must be odd;
the final single element equals the original alternating sum, and it must be positive.

So if a subarray is good, then: $|subarray| \text{ is odd and } a_l-a_{l+1}+a_{l+2}-\dots+a_r>0.$

Nice. But is that also sufficient? Turns out yes. And that’s the whole damn trick.

Observation 2: if the length is odd and the alternating sum is positive, then it is good

We prove this by induction on the odd length.

Base cases

Length $1$ : trivially good.
Length $3$ : the only possible move is on the middle element, and it is legal iff $a_1+a_3>a_2,$ which is equivalent to $a_1-a_2+a_3>0.$ So the statement is true.

Key lemma: any positive array of odd length at least $5$ has at least one legal move

Look at indices $i=2$ and $i=3$ .

If both were illegal, then

\qquad a_3 \ge a_2+a_4.$$ Substitute the first into the second: $$a_3 \ge (a_1+a_3)+a_4 > a_3,$$ which is impossible. So at least one of $i=2$ or $i=3$ is legal. In other words, for any positive array of length $\ge 5$, you can always reduce it once. ### Induction step Suppose an odd-length array has positive alternating sum. Perform any legal move guaranteed by the lemma. The new array: - is still positive (because legality means the new value is $>0$), - still has odd length, - still has the same alternating sum. So its alternating sum is still positive. By induction, the new array is good, hence the original one is good too. Therefore we get the exact characterization: $$\boxed{\text{A subarray is good iff its length is odd and its alternating sum is positive.}}$$ That’s the entire combinatorial part. The rest is counting. ## Observation 3: rewrite subarray alternating sums with prefix sums Define prefix alternating sums on the whole array: $$p_0=0,\qquad p_i=a_1-a_2+a_3-\dots+(-1)^{i-1}a_i.$$ For a subarray $[l,r]$, its alternating sum **starting with plus at $l$** is: $$S(l,r)=a_l-a_{l+1}+a_{l+2}-\dots+(-1)^{r-l}a_r.$$ Using $p$, this becomes: $$S(l,r)=(-1)^{l-1}(p_r-p_{l-1}).$$ We need to count pairs $(l,r)$ such that: 1. $r-l+1$ is odd, i.e. $l$ and $r$ have the same parity; 2. $S(l,r)>0$. Let $i=l-1$ and $j=r$. Then $i<j$, and odd length means $j-i$ is odd, so $i$ and $j$ have opposite parity. Now split by parity of $j$: - If $j$ is odd, then $i$ is even and $$S(l,r)=p_j-p_i,$$ so we need $$p_i<p_j.$$ - If $j$ is even, then $i$ is odd and $$S(l,r)=-(p_j-p_i)=p_i-p_j,$$ so we need $$p_i>p_j.$$ So while sweeping $j$ from left to right, we need: - for odd $j$: count previous **even** prefix indices $i$ with $p_i<p_j$; - for even $j$: count previous **odd** prefix indices $i$ with $p_i>p_j$. This is a textbook Fenwick-tree-after-compression moment. Not glamorous, but brutally effective. ## Data structure The values $p_i$ can be as large as $O(n\cdot 10^9)$, so compress them. Maintain two Fenwick trees: - `even` = counts of prefix sums $p_i$ where $i$ is even, - `odd` = counts of prefix sums $p_i$ where $i$ is odd. Initially, only $p_0=0$ is present in `even`. For each $j=1\dots n$: - let `pos = compressed(p_j)`; - if $j$ is odd, add $$\#\{i<j : i\text{ even},\ p_i<p_j\};$$ - if $j$ is even, add $$\#\{i<j : i\text{ odd},\ p_i>p_j\};$$ - then insert $p_j$ into the Fenwick tree of parity $j$. Each operation is $O(\log n)$, so total complexity is $$O(n\log n)$$ per test case, and across all tests still $$O\left(\sum n \log n\right),$$ which is easily fine for $\sum n\le 2\cdot 10^5$. ## Correctness sketch - By the invariant + induction argument, a subarray is good iff it has odd length and positive alternating sum. - The prefix-sum formula converts that condition into a comparison between $p_{l-1}$ and $p_r$, depending only on parity. - The Fenwick trees count exactly those previous prefix indices with the required parity and inequality. - Every good subarray is counted once when processing its right endpoint $r$, and no bad subarray is counted. Done. No smoke, no mirrors, just one nice invariant and a counting sweep.

Drowning

Progressive nudges

Full explanation

Observation 1: two invariants smack you in the face

Observation 2: if the length is odd and the alternating sum is positive, then it is good

Base cases

Key lemma: any positive array of odd length at least $5$ has at least one legal move

Generated C++

Drowning

Progressive nudges

Full explanation

Observation 1: two invariants smack you in the face

Observation 2: if the length is odd and the alternating sum is positive, then it is good

Base cases

Key lemma: any positive array of odd length at least 555 has at least one legal move

Generated C++

Key lemma: any positive array of odd length at least $5$ has at least one legal move