操作列は「\(1\) 以上 \(N-1\) 以下の整数 \(i\) を選び \(P\) を右に \(i\) 回 shift して、\(P\) を反転する」を \(K\) 回繰り返す、と言い換えられます。

\(P\) を右に \(i\) 回 shift して \(P\) を反転する操作と \(P\) を反転して \(P\) を右に \(N-i\) 回 shift する操作は等しい操作となります。よって、操作列を「\(1\) 以上 \(N-1\) 以下の整数 \(i\) を選び \(P\) を右に \(i\) 回 shift する」を \(K\) 回繰り返し、「\(P\) を反転する」を \(K\) 回繰り返す、と考えても答えは変わりません。

反転操作は \(K\) が偶数なら打ち消され、\(K\) が奇数なら \(1\) 回だけ反転することになるため簡単に考慮出来ます。よって、前半の shift 部分だけ考えることにします。

\(K\) 回の繰り返しによって \(\bmod\ N\) で \(i\) 回 shift する操作列の個数を \(a_i\) と置くと、\(a=(a_0,a_1,\dots,a_{N-1})\) は以下の形を取ります。

• \(K\) が偶数のときは \(a=(v+1,v,v,\dots,v)\)
• \(K\) が奇数のときは \(a=(v-1,v,v,\dots,v)\)

この事実は帰納法や包除原理、FPS の利用によって証明できます。(\(a\) を列挙して観察することでも気付きやすいと思います。)

ここでは FPS を用いて証明をします。求めたい値 \(a_0,a_1,\dots,a_{N-1}\) は \((x+x^2+\dots+x^{N-1})^K \bmod (1-x^N)\) の係数列です。ここで、\(\bmod\ (1-x^N)\) とは \(1-x^N = 0\) とみなす、つまり \(x^N = 1\) として扱うという意味です。

\[ \begin{aligned} & (x+x^2+\dots+x^{N-1})^K \bmod (1-x^N) \\ &= ((1+x+\dots+x^{N-1})-1)^K \bmod (1-x^N) \\ &= \sum_{i=0}^{K} \binom{K}{i} (1+x+\dots+x^{N-1})^i (-1)^{K-i} \bmod (1-x^N)\\ &= (-1)^K + \sum_{i=1}^{K} \binom{K}{i} (1+x+\dots+x^{N-1})^i (-1)^{K-i} \bmod (1-x^N) \\ &= (-1)^K + \sum_{i=1}^{K} \binom{K}{i} N^{i-1} (1+x+\dots+x^{N-1}) (-1)^{K-i} \bmod (1-x^N) \end{aligned} \]

これで示されました。最後の式変形は対称性を利用しています。

\(\sum_{i=0}^{N-1} a_i\) は \((N-1)^K\) なので、\(v\) も簡単に求まります。\(I_i\) を \(P\) を \(i\) 回 右 shift したときの転倒数とすると、求めたい値 \(\sum_{i=0}^{N-1} a_i I_i\) は \((-1)^KI_0 + v \sum_{i=0}^{N-1} I_i\) と変形できます。よって、\(I_0\) と \(\sum_{i=0}^{N-1} I_i\) が管理出来ればよいです。

与えられた \(P\) について転倒数を求めるのも swap クエリに対して転倒数を管理するのも簡単なので、与えられた \(P\) について \(\sum_{i=0}^{N-1} I_i\) を求めることと、swap クエリに対して \(\sum_{i=0}^{N-1} I_i\) を管理することを考えます。

ここからは方針が複数あると思いますが、\(2\) 個の方針を解説します。

\(1\) 個目の方針は、\(\sum_{i=0}^{N-1} I_i\) を以下のように言い換えます。

• 順列 \(Q\) を \(P_{Q_i} = i\) を満たすように取る。この時、\(\sum_{i=0}^{N-1} I_i = \sum_{1 \le i < j \le N} ((Q_j - Q_i) \bmod N) \) が成り立つ。

\(i,j\) のペアが転倒数に加算される回数を主客転倒して見ています。まず、与えられた \(P\) について \(\sum_{i=0}^{N-1} I_i\) を計算します。\(Q\) を求めてから segment tree などで \(f(Q) = \sum_{1 \le i < j \le N} ((Q_j - Q_i) \bmod N)\) を求めればよいです。

\(P\) における隣接 swap は、\(Q_a = x,Q_b = x+1\) なる \((a,b)\) に対する \(Q_a,Q_b\) swap となります。swap によって \((Q_j - Q_i) \bmod N\) がどのように変化をするかを考えます。

\(a < b\) を仮定すると、以下のように場合分け出来ます。

• $i = a,j = b$ のとき、$N-2$ 増える
• $i = a,j \neq b$ のとき、$1$ 減る
• $i \neq b,j = a$ のとき、$1$ 増える
• $i = b,j \neq a$ のとき、$1$ 増える
• $i \neq a,j = b$ のとき、$1$ 減る
• $i,j$ と $a,b$ がどれも一致しないとき、変わらず

\(a > b\) のときも同じように処理できます。よって \(\mathrm{O}(1)\) で \(f(Q)\) の増減が求まります。上記を行うことでこの問題を \(\mathrm{O}(N \log N + Q \log K)\) で解くことが出来ます。

\(2\) 個目の方針は、\(I_{i+1}\) と \(I_i\) の差分に注目する方針です。

\(P\) を \(1\) 回右 shift したときの転倒数の増減に注目します。\(P_N\) が末尾から先頭に移動することによって、\(P_N\) 未満の要素と \(P_N\) は転倒していなかった状態から転倒している状態になります。\(P_N\) 超過の要素と \(P_N\) は転倒していた状態から転倒していない状態になります。よって、\(I_0 + (P_N - 1) - (N - P_N) = I_1\) が成り立ちます。

整理すると \(I_0 + 2P_N - (N+1) = I_1\) となります。一般的に、\(I_i + 2P_{N-i} - (N+1) = I_{i+1}\) が \(i = 0,1,\dots,N-2\) について成り立ちます。

よって、与えられた \(P\) に対して \(\mathrm{O}(N)\) で \(d_i = I_i - I_0\) を列挙できます。また、\(P_i,P_{i+1}\) を swap する際は \(d_{N-i}\) しか変化しません。つまり、\(\sum_{i=0}^{N-1} I_i = NI_0 + \sum_{i=0}^{N-1} d_i\) の増減は \(\mathrm{O}(1)\) で求まります。もしくは segment tree に乗せて計算することも出来ます。こちらの方針でも、\(\mathrm{O}(N \log N + Q \log K)\) で答えが求まります。