考察
query区間の最長同一文字runは、左右子区間内の最大runか、左suffixと右prefixが同じ文字のときその連結runのいずれかである。
merge後のprefix/suffixを正しく延長するには、子区間全体が同じ文字かどうか、または区間長を持つ必要がある。
採用する候補: prefix文字・長さ、suffix文字・長さ、区間全体同一flag、内部最大runをmonoidとしてsegment treeに載せる
隣接二nodeを境界文字の一致でO(1) mergeでき、点更新と任意substring queryを各O(log N)で処理できる。
棄却する候補: 更新後の各type2区間を左から走査してrun lengthを数え直す
一query O(N)となりQ=5×10^5では間に合わず、変更は一点だけなのに既存区間情報を再利用しない。
空要約を先に処理し、非空a,bではsame=(a.suffixChar=b.prefixChar)を求める。best=max(a.best,b.best,same ? a.suffixLen+b.prefixLen : 0)、all=a.all and b.all and same。prefixはa.prefixを引き継ぎ、a.allかつsameの場合だけ長さへb.prefixLenを足す。suffixはb.suffixを引き継ぎ、b.allかつsameの場合だけa.suffixLenを足す。全同一の子でも境界文字が異なれば延長できない。例えば"aa"と"bb"の結合はprefix長2、suffix長2、best2である。
空区間identityを長さ0として特別扱いすれば op(e,x)=op(x,e)=x を保証でき、標準segment treeのrange productをそのまま使える。
各文字をlen=1、prefix=suffix=その文字/1、all=true、best=1のnodeへ変換してbuildする。mergeでlen、all、prefix、suffix、bestを更新する。公式位置pは木のp−1へ対応させて葉を置換する。公式の閉区間[l,r]への照会はprod(l−1,r).bestを出力する。
典型の発動条件
区間summary monoid
発動条件: query答えが左右内部の答えと境界をまたぐ候補から合成できるとき。
prefix/suffix/全体flag/最大値を閉じたmerge情報として持つ。
segment tree
発動条件: 一点更新と結合可能な区間queryが大量にあるとき。
文字leafを更新し、substring nodeをO(log N)で取得する。
問題固有の要素
最長run全体だけでは境界mergeできないため、境界へ接続可能なprefix/suffixを証拠として一緒に保持する。
別の問題へ持ち帰る視点: 部分列の連続構造をsegment tree化するときは、内部最適に加えて左右境界から伸びる未完成解を状態にする。
正当性
結合区間のrunは左内部・右内部・境界をまたぐものの三つに分かれ、境界をまたげるのはsameの場合だけである。prefixが右へ届くには左全体が同一文字で境界も一致する必要があり、その二条件でのみ延長する。suffixも対称で、全体同一は左右全体同一かつsameと同値。従ってmergeの各fieldは実際の連結文字列の要約を表す。文字列の連結は結合的で、この要約も括り方によらない。空文字列の要約を単位元として、指定区間[L−1,R)のfoldはその部分文字列の最長runを返す。
実装上の注意
- prefixは左子allかつ境界一致、suffixは右子allかつ境界一致の場合だけ延長する。空要約は文字比較前に返す。公式の閉区間[l,r]を木の[l−1,r)へ写す。
復習の核
- 長さ1、全同一、境界で二runが結合/分裂する更新、queryがnode境界をまたぐ例をsubstring直接走査と比較する。
計算量と制約
時間
O(N+Q log N)。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: N is an integer between 1 and 5 \times 10^5, inclusive.; S is a string of length N consisting of lowercase English letters.; Q is an integer between 1 and 5 \times 10^5, inclusive.; Type 1 queries satisfy the following constraints: i is an integer between 1 and N, inclusive. x is a lowercase English letter.; i is an integer between 1 and N, inclusive.; x is a lowercase English letter.; Type 2 queries satisfy the following constraints: l,r are integers satisfying 1 \le l \le r \le N.; l,r are integers satisfying 1 \le l \le r \le N.
出典