Official

G - Similar Adjacent Subarrays Editorial by vwxyz Editorial for printing


原案:vwxyz

\(d=b-a\) とし、\(d\) を全探索します。
\(A\) を前から \(d\) 個ごとの要素に区切り、\(A_a\) が含まれる区切りを全探索します。これを \(B\) とし、\(B\) の右の区切りを \(C\)、\(C\) の右の区切りを \(D\) とします。
\(L_i=\begin{cases}1 &(B_i \neq C_i)\\0&(B_i=C_i)\end{cases} \\ R_i=\begin{cases}1 &(C_i \neq D_i)\\0&(C_i=D_i)\end{cases}\)
とします。 \(A_{a+1},A_{a+2},\dots,A_{b}\) のうち \(B\) に含まれるものの個数を \(x\) とすると、\(A_{a+i} \neq A_{b+i}\)​ を満たす \(1\) 以上 \(b−a\) 以下の整数 \(i\) の個数は \(\sum_{i=d-x+1}^{d}{L_i}+\sum_{i=1}^{d-x}{R_i}\) です。 これが \(1\) になるような \(x\) の個数がわかればよいです。
これが \(1\) のとき、\((\sum_{i=d-x+1}^{d}{L_i},\sum_{i=1}^{d-x}{R_i})\) は \((0,1)\) か \((1,0)\) です。 suffix arrayとsparse tableの前計算により連続部分列のLCPを \(O(1)\) で計算できるようにしておくと、それぞれが \(0,1\) となるような \(x\) の区間がわかるため個数を求めることができます。

前計算は \(O(N \log N)\) であり、調べる区切りの個数も \(O(N \log N)\) なので、計算量は全体で \(O(N \log N)\) です。

posted:
last update: