G - Similar Adjacent Subarrays 解説
by
shobonvip
印刷ページ
分割統治で解きます
\(A\) の区間 \([l,r)\) と \(l<m<r\) に対し、2つの区間が \(m\) を(真に)またぐもの、すなわち \(a < m < c\) である解を数えます。この解は
- \(a < m < b < c\)
- \(a < m = b < c\)
- \(a < b < m < c\)
のいずれかを満たします。3. は反転すると 1. と同じ形になるため 1. を数えればよいです。2. はパターンが少ないため、比較的簡単です。

(リンク切れしていたら教えていただきたいです)
1について考察します。上の図のように、 1. の場合 \(m\) をまたぐ2つの区間を 左から4つの区間 \(X_1,Y_1,X_2,Y_2\) に分けます。このとき、2つの区間を数える条件は
- \(X_1, X_2\) は同じかつ, \(Y_1,Y_2\) は 1 文字違う
- \(X_1, X_2\) は 1 文字違うかつ, \(Y_1,Y_2\) は同じ
のいずれかを満たすことです。
高速に数える
\(m\le i < r\) に対し、
- \(A[m-t,m)\) が \(A[i+1-t,i+1)\) と同じである \(t\)
- \(A[m-t,m)\) が \(A[i+1-t,i+1)\) とちょうど1文字違う \(t\)
(\(X_2\) をどのくらい伸ばせるかを表す)
はそれぞれ区間になり、二分探索+Rolling Hash で求めることができます。 また、\(m \le i < r\) に対し
- \(A[m,m+s)\) が \(A[i,i+s)\) と同じである \(s\)
- \(A[m,m+s)\) が \(A[i,i+s)\) とちょうど1文字違う \(s\)
(\(Y_1\) をどのくらい伸ばせるかを表す)
もまた同じように区間となり、二分探索+Rolling Hash で求めることができます。
\(t\) を \(X_2\) のサイズとして、\(i\) を \(X_2\) の右端としたとき、それぞれの条件を満たすものの \(t\) の値は区間となり、さきほど求めた4つを用いて計算を頑張ると求めることができます。
ここで、\(a < m = b < c\) のパターンを数えないように注意することも必要です。
区間のサイズを \(k\) として \(O(k \log k)\) 時間でこれが求まるので、分割統治全体で \(O(N \log^2 N)\) 時間で求まります。
さらなる高速化
二分探索+Rolling Hash パートは計算量を落とせます。
Suffix Array+LCPを求めれば、任意の2つの位置からの最長の共通部分が区間最小値クエリになります。線型RMQやSparse Tableなどを使えばこのパートは分割統治全体で \(O(N \log N)\) になるため、全体の計算量を \(O(N \log N)\) にすることができます。
Main-Lorentz Algorithmとの関連
Run列挙を行う Main-Lorentz Algorithm も似たような分割統治だと思います。
投稿日時:
最終更新:
