この問題は(本質的には同じかもしれないが)おそらく解法が複数ある気がするので自分が本番で解いた方法を記述しておきます。

条件を一旦無視してみると

\(N\) 頂点 \(N\) 辺のグラフで \(i\) 番目の辺は \((i,P_{i})\) を結ぶ辺であるものを考えます。

これの連結成分の数を \(C\) とすると、 \(3\) つ目の条件を無視すれば \(N-C\) 回でできます。

その方法は \(i\neq P_{i}\) である \(i\) を選んで \(\text{swap} (i,P_{i})\) を行えばいいです。

これをすると各連結成分ごとに (連結成分のサイズ) \(-1\) 回でできます。

連結成分ごとに解けばいい

\(\text{swap}(1,1)\) という操作は前後にどのような操作をしても \(3\) つ目の条件をその前後では満たします。

よって、連結成分が \(1\) 個のときに \(N-1\) 回でできれば、各連結成分ごとに \(P_{i}=i\) とした後に \(\text{swap}(1,1)\) を挟むことでこの問題が解けます。

簡単な例を考える

4 1 2 3
# # 
1 4 2 3
  # #
1 2 4 3
    # #
1 2 3 4

この操作を含め、たくさん実験するとわかるかもしれませんが、 \(P_{2}=1\) のときに \(\text{swap}(1,2)\) をする操作は強いです。

なぜなら、この操作の後できない操作は \(l=1\) の場合のみですが、すでに \(P_{1}=1\) なので操作をする必要がないからです。

なので、 \(P_{2}=1\) の形を作って \(\text{swap}(1,2)\) をして、 \(N-1\) の場合に帰着するということを考えたいですが、無理に \(P_{2}=1\) の形を作ると操作回数が最適にならないときがあります。

\(P_{2}=1\) にする

\(P_{i} \rightarrow i\) の \(N\) 頂点の有向グラフを考えます。

このグラフの頂点 \(1\) から頂点 \(2\) のパス上に含まれる頂点集合を \(A\) とし、\(M=|A|\) とします。ただし、 \(A\) に \(1\) は含まず、 \(2\) は含むこととします。 \(P_{A_{1}},P_{A_{2}},...,P_{A_{M}}\) の部分をソートします。

すると、 \(A_{1}=2\) かつ、\(P_{i}=1\) となる \(i\) が含まれていることから、 \(P_{2}=1\) となります。

また、 \(A\) に含まれている \(2\) 以外の全ての要素 \(a\) について、 \(P_{a}=a\) が成り立ちます。

そのあと、 \(\text{swap(1,2)}\) を行うと \(P_{i}\neq i\) となる \(i\) の数は \(N-M\) 個になります。

よって、 \(M\) 個の部分のソートを \(M-1\) 回、 残りの \(N-M\) 個の部分のソートを \(N-M-1\) 回で行うことができれば、 \(\text{swap(1,2)}\) の操作も含めて \(N-1\) 回でソートが可能です。

\(M<N\) かつ \(N-M<N\) であることから \(N\) が小さいケースに帰着できました。

計算量

例えば \(A\) に含まれている部分を陽に持つと \(O(N^{2})\) になります。

なので \(A\) が上述のグラフのパスであることを活かして \(A\) を陽に持たずに計算します。

これは例えば \(min\) のセグメントツリーを使えば計算可能です。

具体的には以下のようにします。

はじめ、\(Q_{i}\) を上述の有向グラフの 頂点 \(1\) からの距離とします。

ただし、 \(Q_{1}=N\) とします。

\(f(l,r)\) を \(l\leq Q_{i}\leq r\) である部分をソートする操作だとするとその中身は以下のようになります。

• \(l=r\) なら \(Q_{i}=l\) となる \(i\) について \(Q_{i}\leftarrow INF\) として終了する。

• \(l\leq Q_{i}\leq r\) を満たす \(i\) のうち小さい方から \(k\) 番目のものを \(a_{k}\) として、 \(f(l,Q_{a_{2}})\) を呼び出す。

• \(\text{swap}(a_{1},a_{2})\) をした後、\(nl:=Q_{a_{2}}\) とし、 \(Q_{a_{2}}\leftarrow Q_{a_{1}}\) そして、\(Q_{a_{1}}\leftarrow INF\) と置換する。

• \(f(nl,r)\) を呼び出す。

計算量は \(O(N\log(N))\) です。

https://atcoder.jp/contests/wtf22-day1-open/submissions/45323015

本番の提出です。