hogecoder

tsutaj 競技プログラミングの記録

第三回アルゴリズム実技検定 N 問題: 入れ替えと並び替え

問題概要

原文はこちら

atcoder.jp

長さ  N の数列  A = \left( a_{i} \right) があり、 A ははじめ昇順にソートされている。この数列に対して以下で説明される操作を合計  Q 回行った後、最終的にできた数列を出力せよ。

  • 整数  1 \leq x \lt N が与えられるので、 a_{x} a_{x+1} を交換する。
  • 整数  1 \leq l \leq r \leq N が与えられるので、 a_{l}, a_{l+1}, \ldots, a_{r} を昇順にソートする。

制約

  •  1 \leq N \leq 2 \times 10^{5}
  •  1 \leq Q \leq 2 \times 10^{5}

解説

愚直にやると間に合いそうにないので、何か発想の転換が必要です。まずはどうやったら時間内に処理できそうかを考えてみましょう。

1 番目のクエリは隣り合っている要素を swap するだけなので簡単に  O(1) で実現可能です。以降、2 番目のクエリをどうするかを考えます。まず、準備のため 転倒数 という概念を次のように定めます。

  • 数列  A = \left( a_i \right) のうち、 1 \leq l \lt r \leq N かつ  a_{l} \gt a_{r} を満たす相異なるインデックス  (l, r) の総数を 転倒数 とよぶ。

例えば  A = \left[ 3, 4, 1, 5, 2 \right] という数列に関して転倒数を考えると、インデックスのペア  (1, 3), (1, 5), (2, 3), (2, 5), (4, 5) について上記の条件を満たすので、転倒数は  5 となります。

さて、はじめに与えられる  A は昇順にソートされていることから、転倒数は  0 であることがわかります。また、 1 番目のクエリにおいて、swap される前の要素に関して  a_{x} \lt a_{x+1} ならば転倒数は  1 増え、 a_{x} \gt a_{x+1} ならば転倒数は  1 減ることがわかります。これらのことから、次のようなことが言えます。

  • ある 2 番目のクエリについて、それ以前に発生した 1 番目のクエリの回数を  q とするとき、2 番目のクエリの対象となる数列の転倒数は 高々  q である。

つまり転倒数が  O(Q) であることが言えるというわけです。ある範囲をソートするという操作は、言い換えるとその範囲内の転倒数が  0 となるようにすることですので、転倒数  q に対して  O(f(q)) (ここで  f(q) は計算量に関する関数) で対処できるようなソートアルゴリズムがあるならば、慣らし計算量  O(f(Q)) で元の問題を解くことができます。

さて、ここで問題となるのはどのようなソートアルゴリズムを持ってくるかですが、自分は本番で  f(q) = q \log qアルゴリズムを作って解きました。次でその概要を簡単に説明します。

ソートアルゴリズム

 a_{k} \gt a_{k+1} を満たす  k の集合を管理することを考えます。初期状態ではこのような要素は存在しないため空集合です。

1 番目のクエリで  a_{x}, a_{x+1} について swap の操作が行われるとき、 (a_{x-1}, a_{x}), (a_{x}, a_{x+1}), (a_{x+1}, a_{x+2}) の高々 3 つのペアについて大小関係が入れ替わる可能性があります。これらを更新することで、次の状態に対応する集合が得られます。この操作は、例えば C++ の場合ですと std::set で  O(\log q) で実現できます。

2 番目のクエリでは  l \leq x \lt r を満たす全ての  x について (これは swap をした結果新たに生まれる  x も含む) swap をすればソートができますが、先程の議論からこのような要素の数は高々  q なので、集合を更新しながら転倒数を減らすのは全体で  O(q \log q) で処理できます。

ソースコード

上の解説とちょっと違います ( a_{k} \gt a_{k+1} を満たす  k+1 の集合を管理してます)

int main() {
    int N, Q; cin >> N >> Q;
    set<int> ind;    
    vector<int> A(N);
    iota(A.begin(), A.end(), 1);
    while(Q--) {
        int t, x, y; cin >> t >> x >> y;
        if(t == 1) {
            x--;            
            for(int k=-1; k<=1; k++) {
                // x+k と x+k+1 との比較 -> x+k+1 のほうを削除
                if(x+k < 0 or x+k+1 >= N) continue;
                if(A[x+k] > A[x+k+1]) ind.erase(x+k+1);
            }
            swap(A[x], A[x+1]);
            for(int k=-1; k<=1; k++) {
                if(x+k < 0 or x+k+1 >= N) continue;
                if(A[x+k] > A[x+k+1]) ind.emplace(x+k+1);
            }
        }
        if(t == 2) {
            x--;            
            while(true) {
                auto ptr = ind.upper_bound(x);
                if(ptr == ind.end() or *ptr >= y) break;

                int u = *ptr - 1;
                for(int k=-1; k<=1; k++) {
                    // u+k と u+k+1 との比較 -> u+k+1 のほうを削除
                    if(u+k < 0 or u+k+1 >= N) continue;
                    if(A[u+k] > A[u+k+1]) ind.erase(u+k+1);
                }

                swap(A[u], A[u+1]);

                for(int k=-1; k<=1; k++) {
                    if(u+k < 0 or u+k+1 >= N) continue;
                    if(A[u+k] > A[u+k+1]) ind.emplace(u+k+1);
                }
            }
        }
    }
    for(int i=0; i<N; i++) printf("%d%c", A[i], " \n"[i + 1 == N]);
    return 0;
}

結構面白い問題だなと思いました。慣らし計算量に関する良い題材ですね。