Strange Operation (Hard Version)

Let’s strip the operation down to what it actually says.

If we choose $i<j<k$, then

$p_i=\max(p_j,p_k)+1=\min(p_j,p_k)+2.$

So the three values are exactly

$x,\ x-1,\ x-2,$

with $x$ at the leftmost chosen index. After the operation, the value at that left index drops by $2$, and the other two values each go up by $1$.

The key thing: the chosen left position only changes by moving down by two ranks among the still-active values. That parity fact is the whole problem. Everything else is data structures and not getting lost in the weeds.

Compress the unfinished problem

Suppose we have already fixed values $1,2,\ldots,t-1$ in the answer. Call the remaining positions/values alive.

Among alive values, define

$\operatorname{rank}(p_i)=\#\{\text{alive values } \le p_i\}.$

So the smallest alive value has rank $1$, the next has rank $2$, and so on.

When an alive element is used as the left element of an operation, its rank decreases by $2$. Therefore:

• odd rank can become rank $1$,
• even rank can never become rank $1$,
• even rank can become rank $2$.

That last bullet matters a lot.

Also, if we successfully make some alive position become the current answer value $t$, then for the remaining positions we can just delete that value from the active set. The exact chain of operations shifts the lower values upward, but after compression the remaining problem is the same kind of problem again. Nice little disappearing act, but legal.

Process positions left to right

At any moment, the first unassigned position is the lexicographically most important one. Call it $i$.

Let $r=\operatorname{rank}(p_i)$.

If $r$ is odd, then $p_i$ can be pulled all the way down to the current smallest answer value $t$. Since $i$ is the leftmost alive position, every other alive position is to its right, so all required helper values are available on the right. We set

$q_i=t,$

remove $p_i$ from the alive values, and continue.

If $r$ is even, then $i$ cannot become $t$. No amount of wishful thinking fixes parity. The best possible value at $i$ is $t+1$.

To make that happen, we first need some later position $j$ to become $t$, then after removing that smaller value, the rank of $p_i$ becomes odd, so $i$ can become $t+1$.

So now the question is: which $j$?

A position can be pulled down to the current smallest value only if:

1. its alive rank is odd;
2. there is no smaller alive value before it, because operations can only use indices to the right.

That means $j$ must be on the chain of prefix minima by value. Starting from $i$, repeatedly jump to the first alive position to the right whose value is smaller. Stop when its rank is odd.

This gives the leftmost feasible $j$, so we set

$q_j=t,\qquad q_i=t+1,$

remove both corresponding values, and continue.

Why is this lexicographically optimal?

• If $\operatorname{rank}(p_i)$ is odd, putting $t$ at $i$ is obviously unbeatable.
• If it is even, putting $t$ at $i$ is impossible, so $t+1$ is the best possible first value at $i$.
• Once $q_i=t+1$ is forced, putting $t$ as far left as possible after $i$ gives the best remaining prefix.

That’s the greedy. It is annoyingly elegant, which is exactly how 3000-rated problems like to be.

Finding the jumps fast

We need two operations:

1. Get the current rank of a value $v$ among alive values.
2. Given a value $v$, find the smallest position among alive values smaller than $v$.

Use:

• a Fenwick tree over values, storing $1$ if the value is alive;
• a segment tree over values, where leaf $v$ stores the original position of value $v$ if alive, otherwise $\infty$.

Then:

$\operatorname{rank}(v)=\text{Fenwick.sum}(v),$

and the next smaller alive position is

$\min\{\operatorname{pos}(x): 1\le x<v,\ x\text{ alive}\},$

which is a range minimum query on the segment tree.

Whenever a value is assigned/removed, update both structures.

Amortized bound

Each position is processed as the leftmost alive position at most once. During the inner jumping chain, an index skipped with even rank becomes odd after a smaller value to its right gets removed, so it will not keep causing chaos forever. Each index is visited only $O(1)$ times.

Each visit costs $O(\log n)$, so the total complexity is

$O(n\log n)$

per test case, with total $n\le 3\cdot 10^5$.

Memory is $O(n)$.