The sequence of operations can be rephrased as: repeat \(K\) times “choose an integer \(i\) with \(1 \le i \le N-1\), right-shift \(P\) by \(i\) positions, and then reverse \(P\).”

The operation “right-shift \(P\) by \(i\) positions and then reverse \(P\)” is equivalent to “reverse \(P\) and then right-shift \(P\) by \(N-i\) positions.” Thus, we can equivalently think of the operation sequence as: repeat \(K\) times “choose an integer \(i\) with \(1 \le i \le N-1\) and right-shift \(P\) by \(i\) positions,” then repeat “reverse \(P\)” \(K\) times, and the answer remains the same.

The reversal operations cancel out if \(K\) is even, and result in a single reversal if \(K\) is odd, so they can be handled easily. We therefore focus on only the shift part.

Let \(a_i\) be the number of operation sequences that shift by \(i\) positions \(\bmod\ N\) after \(K\) repetitions. Then \(a=(a_0,a_1,\dots,a_{N-1})\) takes the following form.

• When \(K\) is even: \(a=(v+1,v,v,\dots,v)\)
• When \(K\) is odd: \(a=(v-1,v,v,\dots,v)\)

This fact can be proved by induction, inclusion-exclusion, or use of FPS. (It can also be noticed by enumerating and observing \(a\).)

Here we prove it using FPS. The desired values \(a_0,a_1,\dots,a_{N-1}\) are the coefficients of \((x+x^2+\dots+x^{N-1})^K \bmod (1-x^N)\). Here, \(\bmod\ (1-x^N)\) means treating \(1-x^N = 0\), that is, \(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} \]

This completes the proof. The last transformation uses symmetry.

Since \(\sum_{i=0}^{N-1} a_i = (N-1)^K\), we can also easily compute \(v\). Letting \(I_i\) be the number of inversions of \(P\) after right-shifting by \(i\) positions, the desired value \(\sum_{i=0}^{N-1} a_i I_i\) can be rewritten as \((-1)^KI_0 + v \sum_{i=0}^{N-1} I_i\). Thus, it suffices to maintain \(I_0\) and \(\sum_{i=0}^{N-1} I_i\).

Computing the number of inversions of the given \(P\) and maintaining the inversion count under swap queries are both straightforward, so we focus on computing \(\sum_{i=0}^{N-1} I_i\) for the given \(P\) and maintaining \(\sum_{i=0}^{N-1} I_i\) under swap queries.

There are multiple approaches from here; we explain two of them.

The first approach rewrites \(\sum_{i=0}^{N-1} I_i\) as follows.

• Take the permutation \(Q\) satisfying \(P_{Q_i} = i\). Then \(\sum_{i=0}^{N-1} I_i = \sum_{1 \le i < j \le N} ((Q_j - Q_i) \bmod N)\) holds.

This is obtained by swapping the roles of objects and subjects when counting how many times each pair \((i,j)\) contributes to the inversion count. First, compute \(\sum_{i=0}^{N-1} I_i\) for the given \(P\). We find \(Q\) and then compute \(f(Q) = \sum_{1 \le i < j \le N} ((Q_j - Q_i) \bmod N)\) using a segment tree or similar structure.

An adjacent swap in \(P\) corresponds to swapping \(Q_a\) and \(Q_b\) for the \((a,b)\) satisfying \(Q_a = x, Q_b = x+1\). We consider how \((Q_j - Q_i) \bmod N\) changes under this swap.

Assuming \(a < b\), we can case-split as follows.

• When $i = a, j = b$: increases by $N-2$.
• When $i = a, j \neq b$: decreases by $1$.
• When $i \neq b, j = a$: increases by $1$.
• When $i = b, j \neq a$: increases by $1$.
• When $i \neq a, j = b$: decreases by $1$.
• When none of $i,j$ match $a,b$: no change.

The case \(a > b\) can be handled similarly. Thus, the change in \(f(Q)\) can be computed in \(\mathrm{O}(1)\) time. By implementing the above, this problem can be solved in \(\mathrm{O}(N \log N + Q \log K)\) time.

The second approach focuses on the difference between \(I_{i+1}\) and \(I_i\).

We look at the change in inversion count when \(P\) is right-shifted by one position. Since \(P_N\) moves from the end to the front, elements less than \(P_N\) go from not being inverted with \(P_N\) to being inverted with \(P_N\). Elements greater than \(P_N\) go from being inverted with \(P_N\) to not being inverted with \(P_N\). Thus, \(I_0 + (P_N - 1) - (N - P_N) = I_1\) holds.

Simplifying, \(I_0 + 2P_N - (N+1) = I_1\). More generally, \(I_i + 2P_{N-i} - (N+1) = I_{i+1}\) holds for \(i = 0,1,\dots,N-2\).

Thus, for the given \(P\), we can enumerate \(d_i = I_i - I_0\) in \(\mathrm{O}(N)\) time. Also, when swapping \(P_i\) and \(P_{i+1}\), only \(d_{N-i}\) changes. That is, the change in \(\sum_{i=0}^{N-1} I_i = NI_0 + \sum_{i=0}^{N-1} d_i\) can be computed in \(\mathrm{O}(1)\) time, or alternatively computed using a segment tree. With this approach as well, the answer can be found in \(\mathrm{O}(N \log N + Q \log K)\) time.