初期 AGC 屈指の難問として名高い AGC014F Strange Sorting を解いたので解法を残しておきます。問題を最初に開いてから AC まで軽く 5, 6 年はかかりました

なお、非想定＋未証明＋ライブラリ殴りの三点セットです。

問題概要

長さ $N$ の順列 $p$ に対して、以下の操作を繰り返す。

$\max_{1\le j \le i} p_j = p_i$ となる $p_i$ （高い項と呼ぶ）を全て抜き出して、順番は変えずに末尾に追加する

$p$ をソートされた状態にするためには、何回操作を行えばいいか答えよ。

例: $p = (3,5,1,2,4)$

$(3, 5)$ が条件を満たすため、$p = (1,2,4,3,5) $ に更新
$(1,2,4,5)$ が条件を満たすため、$p = (3,1,2,4,5)$ に更新
$(3,4,5)$ が条件を満たすため、$ p = (1,2,3,4,5) $ に更新．よって、3回でソート完了

観察

まず観察してみると以下のようなことが分かる。

$k$ 回の操作を行うと、必ず末尾 $k$ 項がソート済みとなる(つまり、末尾のほうが徐々にそろっていく)
また、一度 $i, i+1$ が隣接するとその二項は常に一緒に動く
$p = (1, 3, 5, 7, 2, 4, 6)$ のようなパターンでは、奇数のブロックが動く -> 偶数のブロックが動く ... を繰り返して、ソートするのに $n$ 回かかるような例を作ることができる(シミュレーションが厳しそうな例)

$p$ 全体を更新するシミュレーションはどうやっても無理そうなので、同時に動くものは一気に動かすようなシミュレーションを考えたくなる。

まず $k$ 回目で、高い項となる項のリストの更新を考える。

この時以下のように、更新すると $k$ 回目で高い項となる項のリストを順に計算可能である（図を見た方が分かりやすいかも）。

現在 $i-1$ 回目までのリストの処理が終わっているとする。この時 $i$ 回目に高い項が次に高い項となるタイミングを計算する。
$i$ 回目のリストの末尾の項 $X$ が次に高い項となるタイミングは、その時点での $i+1$ 回目以降のリストの末尾が $X$ より小さい最も早いタイミングになる ($i+1$ 回目移行のリストの末尾は常に単調減少なので、二分探索で見つけることが出来る)
このとき、$X$ が次に高い項となるタイミングの末尾が$Y < X$ であるとすると、 $Y+1$ 以上 $X$ 以下の値ブロックは同時に動く

これを、別の表にすると以下の通り。各値が何回目に高い項になるかを書いていくと、非常にそれっぽい更新が見える。（これはかなり想定解の方向に進んでいそうだな～と感じられる。 in-place でこの数列を更新できるか？と考えたくなる）

ゴリ押し

数列の更新の方針を考えたがそこで何も得られなかったので、$k$ 回目に高い項のリストを高速に計算する怪しげな黒魔術の方向に向かった。（例えば、$p = (1, 3, 5, 7, 2, 4, 6)$ は一項ずつの更新では無理だったが、同時に値をブロックで動かすようにリストを更新出来れば $n$ 回くらいの更新で出来ることから、なかなかこの方針は落とせないんじゃね？という考え（悪巧み）に至った）

このシミュレーションを高速にやる方法を考える。出来れば良い操作は、

各リストの末尾の二分探索
各リストに対して二分探索
各リストの split, join

各数列の末尾は普通に vector で管理すれば二分探索可能。ということで、数列の split, join, 二分探索を同時に行えればよく、これは平衡二分探索木で可能！

kopricky 先生の Treap を使いましょう。

kopricky.github.io

適当なランダムケースを実行したところ、操作回数 133576 回でリストの更新は 1762199 回となっていた。更新回数の見積もりが出来ないけど提出！ AC！終わり！（平衡二分探索木がよく分からなくて、雑に二分探索で log を2個つけたら TLE したのはご愛嬌）

終わりに

証明や撃墜ケースなどが分かる方は教えてください