問題概要
原文はこちら
長さ の数列 があり、 ははじめ昇順にソートされている。この数列に対して以下で説明される操作を合計 回行った後、最終的にできた数列を出力せよ。
- 整数 が与えられるので、 と を交換する。
- 整数 が与えられるので、 を昇順にソートする。
制約
解説
愚直にやると間に合いそうにないので、何か発想の転換が必要です。まずはどうやったら時間内に処理できそうかを考えてみましょう。
1 番目のクエリは隣り合っている要素を swap するだけなので簡単に で実現可能です。以降、2 番目のクエリをどうするかを考えます。まず、準備のため 転倒数 という概念を次のように定めます。
- 数列 のうち、 かつ を満たす相異なるインデックス の総数を 転倒数 とよぶ。
例えば という数列に関して転倒数を考えると、インデックスのペア について上記の条件を満たすので、転倒数は となります。
さて、はじめに与えられる は昇順にソートされていることから、転倒数は であることがわかります。また、 番目のクエリにおいて、swap される前の要素に関して ならば転倒数は 増え、 ならば転倒数は 減ることがわかります。これらのことから、次のようなことが言えます。
- ある 2 番目のクエリについて、それ以前に発生した 1 番目のクエリの回数を とするとき、2 番目のクエリの対象となる数列の転倒数は 高々 である。
つまり転倒数が であることが言えるというわけです。ある範囲をソートするという操作は、言い換えるとその範囲内の転倒数が となるようにすることですので、転倒数 に対して (ここで は計算量に関する関数) で対処できるようなソートアルゴリズムがあるならば、慣らし計算量 で元の問題を解くことができます。
さて、ここで問題となるのはどのようなソートアルゴリズムを持ってくるかですが、自分は本番で のアルゴリズムを作って解きました。次でその概要を簡単に説明します。
ソートアルゴリズム
を満たす の集合を管理することを考えます。初期状態ではこのような要素は存在しないため空集合です。
1 番目のクエリで について swap の操作が行われるとき、 の高々 3 つのペアについて大小関係が入れ替わる可能性があります。これらを更新することで、次の状態に対応する集合が得られます。この操作は、例えば C++ の場合ですと std::set で で実現できます。
2 番目のクエリでは を満たす全ての について (これは swap をした結果新たに生まれる も含む) swap をすればソートができますが、先程の議論からこのような要素の数は高々 なので、集合を更新しながら転倒数を減らすのは全体で で処理できます。
ソースコード
上の解説とちょっと違います ( を満たす の集合を管理してます)
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; }
結構面白い問題だなと思いました。慣らし計算量に関する良い題材ですね。