Artistic Balance Tree

Observation 1: the operation is just an odd-length reversal

In one operation, you choose a center $u$ and length $y$, then swap $a_{u-1} \leftrightarrow a_{u+1},\ a_{u-2} \leftrightarrow a_{u+2},\ \dots$ This is exactly reversing the subarray $[u-y,\ u+y].$ Its length is $2y+1,$ so it is always odd.

That odd length is the first big clue.

Observation 2: index parity is invariant

If an element is at position $p$ inside the reversed segment, after reversal it moves to $p' = (u-y) + (u+y) - p = 2u - p.$ Since $2u$ is even, $p' \equiv p \pmod 2.$ So an element on an odd index can never move to an even index, and vice versa.

That means the array splits into two independent pools:

• elements originally on odd indices,
• elements originally on even indices.

A mark at an odd index can only ever mark an odd-position element. Same for even.

Observation 3: any same-parity element can be brought to the target in one move

This is the real aha.

Suppose some element is currently at position $j$, and the current operation wants to mark index $x$. If $j \equiv x \pmod 2,$ then reverse the odd-length segment $[\min(j,x),\max(j,x)].$ Its center is $(j+x)/2$, an integer because the parities match. After this reversal, the element from $j$ moves exactly to $x$.

So before any operation at index $x_i$, you may choose any currently unmarked element of the same parity and put it at $x_i$ in one operation.

That absolutely kills the hard part.

Observation 4: for one parity, only the number of operations matters

Let:

• $k_{odd}$ = number of $x_i$ that are odd,
• $k_{even}$ = number of $x_i$ that are even.

Now focus on just one parity class, say odd. Suppose there are $c$ odd-index elements total, and there are $k$ odd operations.

What sets of odd elements can we end up marking?

• If $k=0$, obviously none.
• If $k>0$, then at least one odd element must get marked.
• We can mark a new odd element on each of the first $s$ odd operations, for any $1 \le s \le \min(k,c).$
• On the remaining odd operations, we can simply bring back an already marked odd element and mark it again (which changes nothing).

So for that parity, we may choose exactly any number of distinct marked elements $s \in [1,\min(k,c)]$ if $k>0$, and $s=0$ if $k=0$.

Therefore, to maximize the total sum of marked elements for that parity, we just want the best possible sum of $s$ elements from that pool.

And, well, duh: that means the top $s$ values after sorting in descending order.

Greedy reduction

Let $v$ be the values from one parity class, sorted descending: $v_1 \ge v_2 \ge \dots \ge v_{|v|}.$ Define prefix sums $pref_s = \sum_{i=1}^{s} v_i.$

Then the best marked-sum contribution of that parity is:

• $0$, if $k=0$;
• otherwise $\max_{1 \le s \le \min(k,|v|)} pref_s.$

Notice why this is not always just “take as many as possible”: if values become negative, adding more marked elements can make the marked sum worse. Since repeated marks are allowed, you can stop introducing new elements and just re-mark an old one.

That is exactly why sample cases with lots of negative numbers don’t simply take $\min(k,|v|)$ elements.

Final formula

Let

• $S = \sum_{i=1}^{n} a_i$,
• $best_{odd}$ = best marked sum from odd positions,
• $best_{even}$ = best marked sum from even positions.

Then $\text{answer} = S - best_{odd} - best_{even}.$

Because marked and unmarked partition the array.

Correctness sketch

We prove the algorithm is correct.

Lemma 1

An element never changes the parity of its index.

Proof. Under a reversal centered at $u$, position $p$ maps to $2u-p$, which has the same parity as $p$. ∎

Lemma 2

Before an operation marking index $x$, any element currently at a position $j$ with $j \equiv x \pmod 2$ can be moved to $x$ in one operation.

Proof. Reverse the segment $[\min(j,x),\max(j,x)]$. Its length is odd, and reversal sends $j$ to $x$. ∎

Lemma 3

For one parity class with $k>0$ operations and $c$ elements, any number $s \in [1,\min(k,c)]$ of distinct marked elements is achievable.

Proof. On the first $s$ operations of that parity, use Lemma 2 to move $s$ chosen unmarked elements one by one to the queried indices and mark them. On later operations of that parity, move any already marked element there again. ∎

Lemma 4

For fixed $s$, the maximum possible sum of $s$ marked elements from one parity class is the sum of its $s$ largest values.

Proof. This is just sorting 101. Any other $s$-element subset has sum no larger. ∎

Theorem

The algorithm outputs the minimum possible sum of unmarked elements.

Proof. By Lemma 1, odd and even classes are independent. By Lemma 3, for each parity we may choose any allowed number $s$ of distinct marked elements. By Lemma 4, the best choice for that $s$ is the top $s$ values. So the optimal marked sum for each parity is exactly the maximum allowed prefix sum. Summing both parities gives the maximum total marked sum, hence subtracting from $S$ gives the minimum unmarked sum. ∎

Complexity

For each test case, we sort the odd and even lists. So the complexity is $O(n \log n + m),$ which is easily fine under the given limits.

Memory usage is $O(n).$

Pretty clean. The whole trick is realizing the operation looks scary, but parity turns it into a glorified sorting/prefix-sum problem.