ABC 415 F — Max Combo

考察

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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Max Combo の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間monoid要約

主題
  • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 区間monoid要約

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 区間monoid要約

      • 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題