各操作は置換なので、逆置換による打消しができます。これを用いると、 \(L \neq 1\) の場合の答えは、 \(L=1\) の問題を \(2\) 回解いて得た置換から計算できます。

よって \(L=1\) の場合を解きます。

ところで、操作は \((l,r)=(1,1),(1,2),(1,3),\ldots \) と続きます。同じ \(l\) に対する操作は連続しています。ここで、同じ \(l\) に対する操作をすべて行った結果を考えます。 \(N=7,l=1\) の場合の変化を次に示します。

\[ \begin{aligned} &&(1,2,3,4,5,6,7)&&\\ &\rightarrow&(\underline{2},\underline{1},3,4,5,6,7)&&\\ &\rightarrow&(\underline{3},1,\underline{2},4,5,6,7)&&\\ &\rightarrow&(\underline{4},1,2,\underline{3},5,6,7)&&\\ &\rightarrow&(\underline{5},1,2,3,\underline{4},6,7)&&\\ &\rightarrow&(\underline{6},1,2,3,4,\underline{5},7)&&\\ &\rightarrow&(\underline{7},1,2,3,4,5,\underline{6})&& \end{aligned} \]

このように、 \(l=1\) の操作をすべて行った場合はもともと末尾にあった要素が先頭に移動します。

\(l\neq1\) の場合でも数列の先頭 \(l-1\) 項を無視すれば同じ構造です。

よって、 \(l=1,2,3,\ldots,l _ 0\) の操作をすべて行った後の状態は、次のようになります。

\[(N,N-1,\ldots,N-l _ 0+1,1,2, \ldots ,N-l _ 0)\]

\(L=1\) の場合の問題に戻ります。 \(l _ 0\) を適切にとって計算し、残りの操作を愚直に行うと、計算量 \(O(N)\) で答えが求まります。

はじめの議論と合わせて、 Swap Many Times を計算量 \(O(N)\) で解くことができ、十分高速です。

実装例(C++)