まず、アミダクジを順列に対応させます。 アミダクジにおいて、左から \(i\) 本目の縦線からクジを辿り始めると左から \(p_i\) 本目でクジを辿り終わるとします。
恒等的なアミダクジに対応する順列 \(p\) は \(p_i=i\) \((i=1,2,\dots,N)\) です。　

\(N\) 頂点で、\(i\to p_i\) に有向辺を張ったグラフは、複数のサイクルで表されます。ただし、 \(i=p_i\) の時はサイズ \(1\) のサイクルとみなすことにします。
操作前の状態でのサイクルの個数を \(n\) 個とします。

結論から述べると操作回数の最小値は \(N-n\) 回となります。
以下それを示します。

\(N-n\) 回の操作が実現できること

実際に操作方法を構築することで証明をします。

\(N-n\) 回を実現する操作例

アミダクジを上から順に見ていきます。
横線によって、元々左から \(a,b\) 本目にあった縦線がswapされるとします。
\(a,b\) が上記のサイクルの集合において、同じサイクルに属している場合、この横線の真上の同じ位置に横線を追加し、サイクルを更新します。
異なるサイクルに属している場合は何もしません。
これをアミダクジの最も下に至るまで繰り返します。

上記の操作の正当性

この操作を下まで完了する事でサイクルが \(N\) 個、すなわち恒等的なアミダクジに出来ることを示します。
背理法を用います。
操作終了後要素数が \(2\) 以上のサイクルが存在するとします。 そのサイクルで、番号の最も小さいものを \(a\) とし、\(p_b=a,p_a=c\) とします。 この時、

• 操作によってアミダクジの今見ている高さより上に影響が無いこと
• この操作方法によって異なるサイクルの要素が新たに同じサイクルに入ることは無いこと

から、アミダクジを上から辿る過程において、\(a,b\) がswapされる横線は存在しません。
一方、\(a\lt b,\ p_b=a\lt c=p_a\) より、アミダクジのどこかで \(a,b\) はswapが起きており矛盾です。
よって、下まで見終わった時サイクルは \(N\) 個となっています。

操作回数

上記の \(a,b\) 本目の縦線をswapする操作によって、\(p\) は \(p_a,p_b\) のみ値が入れ替わり、その他は変化がありません。
よって、この操作により \(a,b\) を含むサイクルは \(2\) つに分裂します。
従って、\(1\) 回の操作でサイクルの数を \(1\) つずつ増やしていくことができます。
恒等的なアミダクジに対応する順列が \(N\) 個のサイクルで表されることに注意すれば、操作回数は \(N-n\) 回となります。

\(N-n\) 回未満の操作が実現できないこと

操作を逆から見ると, \(N\) 個のサイクルを \(n\) 個のサイクルに減らす問題となります。
\(1\) 回の操作で減るサイクルは高々 \(1\) つであるので、操作回数は少なくとも \(N-n\) 回となります。

操作の構築

構築も上記の操作例に従って行う事が出来ます。
ここでは配列によってサイクルを管理する方法を紹介します。

アミダクジの上端で左から \(i\) 本目の縦線が \(c_i\) 個目のサイクルに属していて、そのサイクルで有向辺の指す先は \(p_i\) であるという情報を配列に持たせます。
横線のswapで \(a,b\) 本目のswapがおこる場合の手順を考えます。

まず、同じサイクルに属しているかの判定は \(c_a,c_b\) の値を比較すればよいです。

次に、同じサイクルに属している場合のサイクル分割方法を考えます。
分割後のサイクルは、\((b,p_a,p_{p_a},{p_{p_{p_a}}},\ldots,b)\) 及び、\((a,p_b,p_{p_b},{p_{p_{p_b}}},\ldots,a)\) となります。 一般性を失わず、\((b,p_a,p_{p_a},{p_{p_{p_a}}},\ldots,b)\) の方が要素数が少ないとします。

\(c\) の値の変更については、\(c_b,c_{p_a},c_{p_{p_a}},\ldots\) の値を適当な値に書き換えればよいです。
\(p\) の値の変更については、\(p_a,p_b\) のみを変更すればよいです。

計算量

計算量を見積もります。 一見すると、最悪ケースで上記の変更は一回あたり \(\Theta(N)\)、最大 \(N\) 回の変更で \(\Theta(N^2)\) であるように思えます。
しかし、\(c\) の値の変更を逆順にみると、これはマージテクに他なりません。
よって、\(c\) の値の変更回数は \(O(N\log{N})\) となります。
要素数の大小の判定も \(p\) を用いて愚直に行っても \(c\) の値の変更と同じ回数で行えます。　

よって、計算量は全体で \(O(N\log{N}+M)\) です。