\(S\) に含まれる ( の index を \(A_1<A_2<\ldots<A_k\) とします。

\(k<\left\lceil\frac{L}{2}\right\rceil\) のときは明らかに不可能です。

操作後の \(S\) の長さ \(L\) の連続部分文字列 \(S[l,l+L-1]\) が美しい文字列であるための条件は以下です。

• \(S[l,l+L-1]\) に含まれる ( のうち先頭 \(\left\lceil\frac{L}{2}\right\rceil\) 文字の index を \(B_1,B_2,\ldots,B_{\left\lceil\frac{L}{2}\right\rceil}\) としたとき、\(l+i-1 \leq B_i \leq l+2i-2\)

( どうしをスワップすることは無意味なので、操作後の \(S[l,l+L-1]\) に含まれる ( のうち先頭 \(\left\lceil\frac{L}{2}\right\rceil\) 文字は元の \(S\) の \(A_s,A_{s+1},\ldots,A_{s+\left\lceil\frac{L}{2}\right\rceil-1}\) 文字目由来であると仮定できます。

このとき、操作回数の最小値は以下の式で表されます。

• \(f(l,s)=\sum\limits_{i=1}^{\left\lceil\frac{L}{2}\right\rceil}\max((l+i-1)-A_{s+i-1},0)+\sum\limits_{i=1}^{\left\lceil\frac{L}{2}\right\rceil}\max(A_{s+i-1}-(l+2i-2),0)\)

この式から、\(l\) を固定したときに \(f(l,s)\) が下に凸であること、そして、\(f(l,s)\) が最小となる \(s\) を \(g(l)\) とおいたときに \(g(l) \leq g(l+1)\) であることが証明できます。

よって、\(f(l,s)\) を高速に計算することさえできれば、尺取り法を用いてすべての \(l\) に対して \(f(l,s)\) の最小値を求めることができます。

\(\sum\limits_{i=1}^{\left\lceil\frac{L}{2}\right\rceil}\max((l+i-1)-A_{s+i-1},0)\) は、\(i-A_i\) であらかじめソートしておくことで、\((l+i-1)-A_{s+i-1}>0\) を満たす \(i\) は区間となるので、BITの区間和取得で高速に計算することができます。

\(l\) を \(1\) 増やすことはコスト関数に定数を加えることで処理可能です。 また、\(s\) を \(1\) 増やすことはBITの一点更新で処理可能です。

\(\sum\limits_{i=1}^{\left\lceil\frac{L}{2}\right\rceil}\max(A_{s+i-1}-(l+2i-2),0)\) も同様に処理可能です。

計算量は \(O(N \log N)\) です。

writer 解：https://atcoder.jp/contests/nadafes2022_day2/submissions/30907177