ヒント \(\rightarrow\) https://atcoder.jp/contests/arc176/editorial/9825

\(2\) つの解法があるため、両方を解説します。

1.\(2\) 値化を適用することによって得られる \(\mathrm{O}(N\log M)\) 解法：https://atcoder.jp/contests/arc176/editorial/9817

2.操作の特徴によって得られる \(\mathrm{O}(N + \log M)\) 解法：本解説

\(1 \le i < j \le N\) を満たす整数対 \((i,j)\) に対して、\(P_i,P_j\) に注目します。\(P_i,P_j\) の操作後の行き先の index を \(a,b\) とします。ここで、操作列であって最終的に集合 \(\{i,j\},\{a,b\}\) の要素が \(k\) 個一致しているようなものの個数を \(x_k\) とします。この \(x_k\) は行列累乗や dp で求めることができ、更に \((i,j)\) に寄らないで決まります。また、\(k\) が一致している \(2\) 個の集合 \(\{a_1,b_1\},\{a_2,b_2\}\) を作る操作列の個数は等しいです。(集合であるため、\(\{3,5\},\{5,3\}\) 等を同一視していることに注意してください。)

ここで、以下の問題を考えます。

集合 $\{i,j\}$ と共通の要素を $k$ 個持つ集合 $\{a,b\}$ であって、$|a-b| = 1$ であるものの個数を求めなさい。

上記の問題の答えを \(y_k\) と置きます。すると、\(P_i,P_j\) が操作後に隣り合っているような操作列の個数は \(\frac{y_0}{\frac{(N-2)(N-3)}{2}} x_0 + \frac{y_1}{2(N-2)} x_1 + \frac{y_2}{1} x_2\) 個となります。(ここで \(k\) が一致しているような \(2\) 個の集合を作る操作列の個数が等しいことを利用しています。)

そして、\(y_0,y_1,y_2\) の値は以下の条件のみから求めることが出来ます。

• \(i = 1\) か？
• \(i + 1 = j\) か？
• \(j = N\) か？

よって、全ての整数対 \((i,j)\) に対して \(y_0,y_1,y_2\) を求めて \(|P_i - P_j| \times \left(\frac{y_0}{\frac{(N-2)(N-3)}{2}} x_0 + \frac{y_1}{2(N-2)} x_1 + \frac{y_2}{1} x_2 \right)\) の総和を取ることでこの問題を \(\mathrm{O}(N^2)\) で解くことが出来ます。

さて、このアルゴリズムを高速化しましょう。上記の \(3\) 個の条件のどれを満たすかとしてあり得る \(8\) パターンそれぞれに対して、\(|P_i - P_j|\) の総和が求まればよいです。

ここで、上記の \(3\) 個のうちいずれか \(1\) 個を満たしている \((i,j)\) の組は高々 \(\mathrm{O}(N)\) 通りであるためそれぞれに対して愚直に処理した後、全体からそれらの総和を引くことでどれをも満たさないパターンについても処理をすることが出来ます。よって、\(\mathrm{O}(N)\) でこのパートを解くことが出来ます。

上記を組み合わせることによってこの問題を \(\mathrm{O}(N + \log M)\) で解くことが出来ます。

実装例