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

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

1.\(2\) 値化を適用することによって得られる \(\mathrm{O}(N\log M)\) 解法：本解説

2.操作の特徴によって得られる \(\mathrm{O}(N + \log M)\) 解法：https://atcoder.jp/contests/arc176/editorial/9818

\(\sum_{i=1}^{N-1} |P_i - P_{i+1}|\) は、以下を \(k=1,2,\dots,N-1\) において足し合わせた値に一致します。

• \(1 \le i \le N-1\) かつ \(\min(P_i,P_{i+1}) \le k < \max(P_i,P_{i+1})\) となる \(i\) の個数

これはつまり、\(P\) の \(k\) 以下の値を \(0\) に、\(k\) より大きい値を \(1\) に置き換えて問題の操作を行い、\(\sum_{i=1}^{N-1} |P_i - P_{i+1}|\) の総和を求め、その総和を全ての \(k(1 \le k \le N-1)\) に対して足し合わせれば元の問題の答えが得られるということです。

さて、\(P\) の要素が全て \(0\) か \(1\) の場合の問題を解きます。各 \(i\) に対して操作終了時に \(|P_i - P_{i+1}| = 1\) となる操作列の個数を求めることを考えましょう。これは、\(P_i,P_{i+1}\) のうち \(0\) が \(j(0 \le j \le 2)\) 個あるという \(3\) 状態を持つ行列累乗を行うことによって求めることが出来ます。

上記を全ての \(i,k\) に対して行うと計算量が \(\mathrm{O}(N^2 \log M)\) となりますが、累積和等を用いて各 \(k\) に対して初期状態で \(P_i,P_{i+1}\) のうち \(k\) 以下であるものが \(j\) 個であるような \(i\) の個数を求めておくことによって、各 \(k\) に対しての答えを \(\mathrm{O}(\log M)\) で求めることが出来ます。よって、この問題を \(\mathrm{O}(N \log M)\) で解くことが出来ます。

実装例