Nah, I will continue my Fibonacci streak (21st place -> 13th place -> 8th place).
rocks03 will win.

Let's modify slightly the algorithm. Instead of choosing $$$[x, m]$$$ iff the suffix minimums of $$$[l, m]$$$ are less than the prefix minimums of $$$[m, r]$$$, let's choose $$$[x, m]$$$ iff the minimum of $$$[l, r]$$$ is in $$$[m, r]$$$. Moreover, let's do D&C in reverse order (let's process $$$[l, m-1]$$$ and $$$[m+1, r]$$$, then $$$[l, r]$$$.)

Lemma 1 (quite obvious): in the new algorithm, there aren't in total less candidate minimums than in the previous one.

Lemma 2: in the new algorithm, each $$$A_i$$$ can be a candidate minimum at most twice (once as a prefix minimum, once as a suffix minimum).

Proof of Lemma 2: let's assume that the minimum of $$$[l, r]$$$ is in $$$[m, r]$$$ (the other case is symmetric). If $$$A_i$$$ is a suffix minimum of $$$[l, m]$$$, it can't be a suffix minimum of any interval that contains $$$[l, r]$$$. So, $$$A_i$$$ will never be visited anymore as a suffix minimum after processing $$$[l, r]$$$.

Therefore, both the algorithms visit $$$O(n)$$$ candidate minimums in total.

Yes, we knew about the similarity in the statement with ICPC-WF2021-D, but the solution is completely orthogonal (this one is much harder in fact).

I will quickly describe a subquadratic solution (with complexity $$$O(n^{2-10^{-20}})$$$, that is to say that the complexity estimate is not good) which performs fast enough (it solves instances with $$$n=100\,000$$$ within the time limit, and it is not optimized at all). The general idea is similar to the one you outlined to tackle the random case, but much more ideas are required (and it is much harder to implement).

A prefix move is a move on an odd antipalindrome prefix, a maximal prefix move is the prefix move on the longest antipalindrome prefix. The definitions are analogous for suffix moves.

Observation 1: The optimal solution performs only maximal prefix or suffix moves.

This observation is crucial also to get the quadratic subtask.

Observation 2: The total size of maximal antipalindrome substrings is $$$O(n\log(n))$$$.

This observation is necessary to perform some of the operation described below in pseudolinear time.

Description of the solution: Let us iterate on the number of initial suffix moves performed by the optimal solution.

After executing the suffix moves, we remain with $$$s[0, r]$$$. Let $$$r'$$$ be the center of the maximal antipalindrome suffix of $$$s[0,r]$$$. We may assume that the optimal solution now performs prefix moves until it performs a prefix move on a substring intersecting $$$[r', r]$$$ (otherwise it was convenient to perform one more initial suffix move).

Then, we recur on the subproblem $$$s[l, r]$$$ which remains after performing the described amount of prefix moves. One can show that the total size of the problems we recur at depth $$$1$$$ is bounded by $$$2n$$$ and that all subproblems have size bounded by $$$\frac34 n$$$.

What I have explained is really hard to implement in pseudolinear time (i.e., finding all the substrings one needs to recur on) but is possible.

If we reach a substring with size $$$<L$$$, we change approach and we use the quadratic algorithm to solve the problem with complexity $$$O(nL)$$$ for all short substrings. Choosing $$$L$$$ appropriately yields a subquadratic algorithm and, more importantly, choosing $$$L\approx 200$$$ is sufficient to solve the problem.

Final remark: I have been very concise. If we ever write down the editorial for the problems in english (rather unlikely) I will link it here.

Please put the author :D