G - Similar Adjacent Subarrays 解説 by shobonvip 印刷ページ


分割統治で解きます

\(A\) の区間 \([l,r)\) と \(l<m<r\) に対し、2つの区間が \(m\) を(真に)またぐもの、すなわち \(a < m < c\) である解を数えます。この解は

  1. \(a < m < b < c\)
  2. \(a < m = b < c\)
  3. \(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 も似たような分割統治だと思います。

https://pazzle1230.hatenablog.com/entry/2019/11/27/234632

投稿日時:
最終更新: