本解説では文字列などの表記について特有の記号を用いるため，必要に応じて以下で確認されたい．

解説で用いる記号

• 以下では可算無限個の文字の列 $c_0 c_1 c_2 \dots$ も文字列とよぶ．長さが有限の文字列を有限文字列，長さが無限の文字列を無限文字列という．(無限文字列も含めた) 文字列同士の辞書式順序を，通常の有限文字列に対する辞書式順序と同様に定める (これも全順序となっている．証明は省略する).
• 文字列 $X = x_0 x_1 \dots$ と $0 \leq l \leq r \leq |X|$ に対し，$X$ の部分文字列 $x_l x_{l+1} \dots x_{r-1}$ を $X[l, r)$ で表す．
• 有限文字列 $X$ と文字列 $Y$ について，これらの結合を $X * Y$, または単に $XY$ で表す．
• 有限文字列 $X$ と整数 $n \geq 0$ に対し，$n$ 個の $X$ を結合して得られる文字列を $X^n$ で表す．また $X$ の無限個の結合として得られる(無限)文字列を $X^\infty$ で表す．例えば arc$^3=$ arcarcarc, abc$^\infty=$abcabcabca... である．
• 文字列 $X, Y$ について，それらの最長共通接頭辞の長さを $\text{lcp}(X, Y)$ で表す．
• 文字列 $X, Y$ が $|X| \leq |Y|$ かつ $X = Y[0, |X|)$ を満たすとき，$X$ は $Y$ の prefix であるという．また，さらに $|X| < |Y|$ のとき，$X$ は $Y$ の proper prefix であるという．
• 有限文字列 $X, Y$ が $|X| \leq |Y|$ かつ $X = Y[|Y|-|X|, |Y|)$ を満たすとき，$X$ は $Y$ の suffix であるという．
• 文字列からなる列 $X = (X_1, \dots, X_n)$ に対し，$X$ の転倒数を $\text{inv}(X) \coloneqq | \lbrace (i, j) \mid 1 \leq i < j \leq N, X_i > X_j \rbrace |$ で表す．

文字列に関する補題

解法の説明の前に，文字列に関する補題を 2 つ挙げる．証明はいずれも本解説の末尾に記載する．

補題 1

\(X, Y\) を空でない有限文字列とする．

1. \(X^\infty = Y^\infty \iff XY = YX\) が成り立つ．
2. \(X^\infty \neq Y^\infty\) のとき，\(\text{lcp}(X^\infty, Y^\infty) = \text{lcp}(XY, YX)\) が成り立つ．

補題 2

空でない有限文字列 \(X, Y\) について，\(XY < Y \iff X^\infty < Y\) が成り立つ．

問題の言い替え

各文字列の末尾に共通の文字を加える操作と，文字列同士の隣接 swap を行う操作は入れ替えても結果に影響しない．よって先に文字を加える操作の全てを行ってから隣接 swap を行うことを考えると，この問題は以下の問題と等価になる．

• 有限文字列 \(X\) に対し，\(f(X) = \text{inv}(S_1 X, S_2 X, \dots, S_N X)\) とする．\(|X| + f(X)\) を最小化せよ．

転倒数の変化量

\(S\) を文字列の列 \(S = (S_1, S_2, \dots, S_N)\) とする．また文字列 \(X\) に対し，\(S(X) = (S_1 X, S_2 X, \dots, S_N X)\) とする．文字列 \(X\) を追加した際の転倒数の変化量，すなわち \(\text{inv}(S(X)) - \text{inv}(S)\) がどのような値になるか考える上では，\(S_i\) と \(S_j\) の順序と \(S_i X\) と \(S_j X\) の順序が異なる組 \((i, j)\) についてだけ考えればよい．

\(1 \leq i, j \leq N, i\neq j\) である組 \((i, j)\) に対し，\(S_i X\) と \(S_j X\) の順序がどうなるかを考える．一般性を失うことなく，\(|S_i| \leq |S_j|\) としてよい．

\(S_i\) が \(S_j\) の proper prefix ではないとき，任意の有限文字列 \(X\) に対して \(S_i X < S_j X \iff S_i < S_j\) が成り立つ．よって文字列 \(X\) を加える前後で \(S_i\) と \(S_j\) の順序は変化しない．

\(S_i\) が \(S_j\) の proper prefix であるとき，すなわち空でない有限文字列 \(T\) が存在して \(S_j = S_i T\) であるときを考える．\(S_i\) は \(S_j\) の proper prefix であるため \(S_i < S_j\) である．一方，\(S_i X\) と \(S_j X = S_i TX\) の順序は \(X\) と \(TX\) の順序に等しいが，補題 2 よりこれは \(X\) と \(T^\infty\) の順序に等しい．よって \(S_i\) と \(S_j\) の順序が逆転することと，\(T^\infty < X\) は同値である．

以上をふまえると転倒数の変化量は以下のようになる： \(P \coloneqq \{(i, j) \mid 1 \leq i, j, \leq N, S_i\text{ は }S_j\text{ の proper prefix}\}\) とする．また \((i, j) \in P\) に対し，\(T_{ij}\) を \(S_j = S_i T_{ij}\) を満たす文字列とする． このとき，

\[ \begin{aligned} \text{inv}(S(X)) - \text{inv}(S) = |\lbrace(i, j) \in P \mid i < j, T_{ij}^\infty < X\rbrace| - |\lbrace(i, j) \in P \mid i > j, T_{ij}^\infty < X\rbrace| \end{aligned} \]

が成り立つ．

解法

\(T_{ij}\) は \(S_j\) の suffix であるから，\(T_{ij}\) としてありうる文字列は高々 \(L \coloneqq \sum_i |S_i|\) 通りしかない．各 \(S_j\) の各 suffix \(T\) に対して，\(T^\infty < X\) である場合の転倒数の変化量をあらかじめ求めておく．これは，trie や rolling hash を用いて適切に実装することで \(O(L)\) 時間，または \(O(L\log L)\) 時間で行える．この際，\(S_i\) が distinct でないことに気をつける．

次に，各 suffix の無限回の繰り返しどうしを辞書順でソートする．\(X^\infty\) と \(Y^\infty\) の順序を比較する際には，まず \(l \coloneqq \text{lcp}(XY, YX)\) を計算する．補題 1 より，\(l = |X|+|Y|\) の場合は \(X^\infty = Y^\infty\) であり，そうでない場合は \(X^\infty\) の \(l\) 文字目 (0-based) と \(Y^\infty\) の \(l\) 文字目を比較することで \(X^\infty\) と \(Y^\infty\) の比較が行える．\(l\) の計算については，例えば hash と二分探索を用いれば \(O(\log L)\) 時間かかる．また suffix array, LCP array, sparse table を用いて \(O(L \log L)\) 時間の前処理を行っておけばクエリ当たり \(O(1)\) 時間で済む (本問ではここまでは要求していない)．以上よりこのソートの計算量は \(O(L \log L)\) または \(O(L (\log L)^2)\) である．

さらに，ソート済みの suffix の列において隣り合った \(2\) つの suffix \(A, B\) について，\(A^\infty < X < B^\infty\) を満たす \(X\) における \(|X|\) の最小値を求める．これは \(\text{lcp}(A^\infty, B^\infty) + 1\) に等しく，ソートのときと同様の手順で求めることができる．あとは転倒数への寄与の合計を累積和として保持しておくことで，\(|X| + f(X)\) の最小値を更新していくことができる．この際以下の事項に気をつける．

• z\(^\infty\) より大きい文字列は存在しないこと．
• 違う文字列どうしでもそれらの無限回の繰り返しどうしが等しくなりうること．

---

付録 各補題の証明

補題 1 の証明

1. \(X = x_0x_1\dots x_{|X|-1}, Y=y_0y_1\dots y_{|Y|-1}, g = \text{gcd}(|X|, |Y|)\) とする．より強く，以下の 3 条件が全て同値であることを示すことによって主張が得られる．
   1. \(X^\infty = Y^\infty\).
   2. \(X, Y\) はともに \(g\) を周期としてもつ．
   3. \(XY = YX\).

(ii. \(\Rightarrow\) i.), (ii. \(\Rightarrow\) iii.) は明らかなので，(i. \(\Rightarrow\) ii.), (iii. \(\Rightarrow\) ii.) を示す．

(i. \(\Rightarrow\) ii.)

整数 \(i, j\) が \(0 \leq i < |X|, 0 \leq j < |Y|, i \equiv j \bmod g\) を満たすとする．中国剰余定理により，ある整数 \(k \geq 0\) が存在して \(k \equiv i \bmod |X|, k \equiv j \bmod |Y|\) が成り立つ．\(X^\infty = Y^\infty\) の \(k\) 文字目を比較することで \(x_i = y_j\) が分かる．同様に \(x_{i + g} = y_j\) であるので，\(x_i = x_{i+g}\) である．よって \(X\) は \(g\) を周期としてもつ．\(Y\) についても同様である．

(iii. \(\Rightarrow\) ii.)

一般性を失うことなく \(|X| \leq |Y|\) としてよい．\(XY = YX\) の各部分を比較することで \(Y[0, |X|) = Y [|Y| - |X|, |Y|) = X, Y[|X|, |Y|) = Y[0, |Y|-|X|)\) が分かる．よって \(Y^\infty\) は \(|X|\) を周期としてもつ．\(|Y|\) も明らかに \(Y^\infty\) の周期であるから，結局 \(g = \gcd(|X|, |Y|)\) も \(Y^\infty\) の周期である．よって \(g\) は \(Y\) の周期である．



2. \(X^\infty \neq Y^\infty\) であるとする．1. より \(XY \neq YX\) である．一般性を失うことなく \(|X| \leq |Y|\) としてよい．\(Y\) が \(X^\infty\) の prefix であるかどうかで場合分けをする．

   \(Y\) が \(X^\infty\) の prefix のとき

   このとき，\(|X| \leq |Y|\) より \(X\) は \(Y\) の prefix である．よって \(XY, YX\) はそれぞれ \(X^\infty, Y^\infty\) の prefix である．\(XY \neq YX\) および \(|XY| = |YX|\) より，\(\text{lcp}(X^\infty, Y^\infty) = \text{lcp}(XY, YX)\) である．

   \(Y\) が \(X^\infty\) の prefix でないとき

   \(Y = X^n Y'\) かつ \(X\) が \(Y'\) の prefix ではないような文字列 \(Y'\) と整数 \(n \geq 0\) をとる．\(Y\) が \(X^\infty\) の prefix でないことから，\(Y'\) は \(X\) の prefix ではない．よって \(\text{lcp}(X, Y') < \min\lbrace |X|, |Y'| \rbrace\) であるから，以下が成り立つ．

   \[ \begin{aligned} \text{lcp}(X^\infty, Y^\infty) & = \text{lcp}(X^nX^\infty, YY^\infty) \\ & = \text{lcp}(X^n*X^\infty, X^n*Y'Y^\infty) \\ & = n|X| + \text{lcp}(X^\infty, Y'Y^\infty) \\ & = n|X| + \text{lcp}(X, Y') \\ & = n |X| + \text{lcp}(XY', Y'X) \\ & = \text{lcp}(X^{n+1}Y', X^nY'X) \\ & = \text{lcp}(XY, YX). \end{aligned} \]

\(\blacksquare\)

補題 2 の証明

\(Y = X^n Y'\) かつ \(X\) が \(Y'\) の prefix ではないような文字列 \(Y'\) と整数 \(n \geq 0\) をとる．このとき

\[ \begin{aligned} XY < Y & \iff X^{n+1} Y' < X^{n} Y' \\ & \iff X Y' < Y' \\ & \iff X < Y' \ (\because X \text{ は } Y' \text{ の prefix でない}) \\ & \iff X^\infty < Y\\ \end{aligned} \]

であるから，主張が従う．\(\blacksquare\)