Swap and Sort [第三回 アルゴリズム実技検定 N]

https://atcoder.jp/contests/past202005-open/tasks/past202005_n

解説

https://atcoder.jp/contests/past202005-open/submissions/14080549

tsutajさんの解法, 公式解説にとてもエレガントな説明が書いてある。
久々に目が覚めるような経験をした。なるほど。
エレガントすぎる解説は気づくまでが厳しかったりもするので、ここではもうちょっと泥臭く書いていこうと思う。

クエリ1ではスワップが行われており、クエリ2では区間ソートを行っている。
ソートでスワップといえばバブルソートであるから…と考察を進めていってほしかったのであろう。

用語ばかりを並べてもアレなので、雰囲気を今から話す。
区間ソートを行うときに、それまでに行ったスワップ操作を逆に行うことで区間ソートが実現できそうな感じがする。
つまり、「区間ソートをスワップで行った時の回数」＝「クエリ1でのスワップ回数」っぽくなるということだ。
雰囲気ですよ。雰囲気。
なので、方針としては区間ソートはスワップ（バブルソート）で行う事にすると、スワップ回数はこれまでのクエリ1の回数には抑えられるので、
『ならし』Q回くらいには収まる。
ならしという表現は難しい表現だが、BFSでqueueを使うとO(N)が達成できるが、それだ。
BFSの場合は入れると出すが1回ずつなのでO(N)だが、この問題だと、クエリ1でスワップされるとソートのスワップで戻されるが1回ずつなのでO(Q)。

先にクエリ2に注目して考える。
ある区間ソートをスワップでやろうと思った時のアルゴリズムは、区間中のある隣接要素についてA[i]>A[i+1]を満たすものがあればスワップし続けるという操作。
スワップし続けるとある時、全部A[i]<A[i+1]となって止まるが、それがソート完了。
なので、素早く「区間中のある隣接要素についてA[i]>A[i+1]を満たすもの」を取ってくる必要があるが、setで管理する。
badpairs := A[i]>A[i+1]であるiの集合
lower_boundでx以上のものを取ってきてポンポンスワップすればいい。

これでクエリ1もクエリ2もスワップ操作に帰着できた。
どちらも自分の実装ではmyswap関数を作ってやっている。
スワップ時はA[i],A[i+1]のスワップするので、大小関係的には(i-1,i),(i,i+1),(i+1,i+2)が変化しうる。
なので、スワップ前にそれらの情報がbadpairsに入っていれば消して、スワップ後に、大小関係を見てA[i]>A[i+1]になっていれば入れなおせばいい。

int N, Q, A[201010];
//---------------------------------------------------------------------------------------------------
set<int> badpairs;
// swap the x-th item and the (x+1)-th item
void myswap(int x) {
    rep(d, -1, 2) if (badpairs.count(x - d)) badpairs.erase(x - d);
    swap(A[x], A[x + 1]);
    rep(d, -1, 2) if (0 <= x + d && x + d + 1 < N && A[x + d] > A[x + d + 1]) badpairs.insert(x + d);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) A[i] = i + 1;
    badpairs.insert(inf);

    rep(_, 0, Q) {
        int t, x, y; cin >> t >> x >> y;
        x--; y--;

        if (t == 1) {
            myswap(x);
        }
        else {
            while (true) {
                auto ite = badpairs.lower_bound(x);
                if (y <= *ite) break;
                myswap(*ite);
            }
        }
    }

    rep(i, 0, N) {
        if(i) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
}