ABC 331 F — Palindrome Query

考察

回文であるとは、左から読んだ文字列と右から読んだ文字列が同じであることだ。この二つを短いハッシュ値で表し、隣り合う区間から全体の値を作れれば、一文字の変更後も必要な区間だけを調べられる。

長さ NN の文字列に QQ 回の操作が入る。毎回両端から文字を比較すると、最悪で O(NQ)O(NQ) 時間になる。静的な文字列なら回文半径の前計算も使えるが、一点の変更で多数の半径が変わり得る。そこで、変更の影響をその位置を含む区間だけにとどめるため、Segment Treeへ載せる情報を考える。

回文かどうかの代わりに、両向きの列を覚える

「左右の区間がそれぞれ回文か」だけでは、連結後の回文判定はできない。例えば、一文字の区間はすべて回文だが、連結した aa は回文、ab は回文でない。連結後を調べるには、文字の並び順に関する情報が要る。ただし、文字列そのものを各節点へ持つと、結合のたびに長い文字列を扱うことになる。

ここで、列・文字列のrolling fingerprintの多項式ハッシュを使う。文字を a は1、b は2、…、z は26という異なる整数へ写す。素数 p>26p>26 を法、1≤B<p1\leq B<p を基数とし、以降のハッシュの計算はすべて法 pp で行う。同じ法と基数を、すべての区間・操作で共通に使う。

長さ mm の文字列 TT の各文字に対応する数を、左から c0,c1,…,cm−1c_0,c_1,\ldots,c_{m-1} とする。順方向のハッシュ f(T)f(T) と逆方向のハッシュ r(T)r(T) を、次で定める。

f(T)=∑i=0m−1ciBm−1−i(modp),r(T)=∑i=0m−1ciBi(modp).\begin{aligned} f(T)&=\sum_{i=0}^{m-1}c_i B^{m-1-i}\pmod p,\\ r(T)&=\sum_{i=0}^{m-1}c_i B^i\pmod p. \end{aligned}

順方向では左の文字ほど高い桁へ置き、逆方向では右の文字ほど高い桁へ置く。したがって r(T)r(T) は、TT を逆順にした文字列の順方向ハッシュに等しい。回文なら二つの値は必ず等しい。一方、異なる列が同じハッシュ値になる衝突があり得るので、逆は無条件には成り立たない。誤判定の評価は正当性節で扱い、まずハッシュそのものを正しく更新・取得する方法を導く。

結合で必要になるのは、隣の区間の長さ分の桁移動

短い例として、左区間を ab、右区間を c とする。

f(ab)=B+2,f(c)=3,r(ab)=1+2B,r(c)=3.\begin{aligned} f(\text{ab})&=B+2,&f(\text{c})&=3,\\ r(\text{ab})&=1+2B,&r(\text{c})&=3. \end{aligned}

連結した abc の順方向ハッシュは (B+2)B+3(B+2)B+3。右に一文字を足したため、左区間の各項を一桁上げる。一方、逆方向ハッシュは (1+2B)+B2⋅3(1+2B)+B^2\cdot 3。右区間の文字は、左区間の二文字分だけ指数が大きくなる。

一般に、左の文字列を UU、右の文字列を VV とし、UVUV をその順の連結と書く。上の桁移動をそのまま式にすれば、

f(UV)=f(U)B∣V∣+f(V)(modp),r(UV)=r(U)+B∣U∣r(V)(modp).\begin{aligned} f(UV)&=f(U)B^{|V|}+f(V)\pmod p,\\ r(UV)&=r(U)+B^{|U|}r(V)\pmod p. \end{aligned}

ここで ∣U∣,∣V∣|U|,|V| は各文字列の長さである。順方向では右の長さ、逆方向では左の長さを使う。逆から読むと VV を逆にした列の後ろへ UU を逆にした列が続く、と考えても同じ式を得られる。

結合のたびに冪を計算せずに済むよう、q(T)=B∣T∣ mod pq(T)=B^{|T|}\bmod p も覚える。一つの区間の要約を h(T)=(f(T),r(T),q(T))h(T)=(f(T),r(T),q(T)) とすれば、結合は次の三つの計算になる。

f(UV)=f(U)q(V)+f(V)(modp),r(UV)=r(U)+q(U)r(V)(modp),q(UV)=q(U)q(V)(modp).\begin{aligned} f(UV)&=f(U)q(V)+f(V)\pmod p,\\ r(UV)&=r(U)+q(U)r(V)\pmod p,\\ q(UV)&=q(U)q(V)\pmod p. \end{aligned}

最後の式は B∣U∣+∣V∣=B∣U∣B∣V∣B^{|U|+|V|}=B^{|U|}B^{|V|} による。これで、結合後も次の結合に必要な情報がそろう。長さそのものを別に保存しなくてもよい。

空文字列の要約は (0,0,1)(0,0,1) とする。例えば右にこれを結合すると、順方向は f⋅1+0=ff\cdot 1+0=f、逆方向は r+q⋅0=rr+q\cdot 0=r、基数冪は q⋅1=qq\cdot 1=q となる。左に置いても変わらず、これが単位元である。値が dd の一文字の要約は (d,d,B)(d,d,B) になる。

葉の変更と、順序を保った区間取得へつなぐ

各葉に一文字の要約を置き、各内部節点には左の子と右の子をこの順で結合した要約を置く。結合則により、取得区間をどの節点に分解しても、左から並べて結合すれば同じ要約を得られる。この点が区間monoid要約の使いどころである。

以下では文字列の添字を0始まりとし、区間は左端を含み右端を含まない半開区間で扱う。

  1. 全文字の葉を作り、子から親へ順に結合して木を構築する。
  2. 更新 1 x c では、位置 x−1x-1 の葉を新しい文字の要約へ置き換え、根まで再計算する。
  3. 判定 2 L R では、半開区間 [L−1,R)[L-1,R) の要約を取得する。この区間の長さは R−L+1R-L+1 である。
  4. 取得した順方向・逆方向ハッシュを比較し、一致した場合に回文と判定する。衝突を減らすため、後述のように複数の独立な基数で同じ木の要約を持ち、すべての組で一致するときだけ Yes、それ以外は No を返す。

長さ1では常に両方向が同じ値になる。偶数長・奇数長とも中央で分割する必要はなく、同じ区間取得と比較で処理できる。

典型の発動条件

Rolling Hashの結合monoid

答えだけで結合できなければ、比較対象の表現を要約する。 区間全体の真偽を左右の真偽から作れないときは、何と何が一致すればよいかへ戻る。列の順序付きの一致なら、多項式ハッシュが候補になる。ただし衝突を許す確率的な判定である。

連結後も次の結合に使う情報を残す。 ハッシュ値だけでなく、桁移動に要る基数冪まで保持すると、一定サイズの要約を一定時間で結合できる。

segment treeによる動的文字列query

一点更新と順序付きの区間集約を組み合わせる。 結合則と単位元を確認できればSegment Treeを使える。結合則が許すのは括る位置の変更であり、左右の入れ替えではない。

問題固有の要素

回文の定義が「同じ区間を両向きに読んだ列の一致」なので、各区間について二方向のハッシュを組にすればよい。反転した文字列を別に管理する必要はなく、一文字の変更も一つの葉の両方向へ同時に反映できる。同じ区間の比較なので、両方向の長さは初めから等しい。

正当性

まず、ハッシュの取得が正しいことと、そこから回文と判定するときの誤りを分ける。各節点が表す区間の実際の文字列を TT とすると、その節点には定義どおりの h(T)h(T) が入る、という不変条件を保つ。

葉の (d,d,B)(d,d,B) は一文字の定義に一致する。内部節点の式も、左区間の後ろへ右区間を連結したときの桁移動そのものなので、正しい子から正しい親を作れる。三つの文字列の連結結果は括る位置によらないから、この要約の結合も結合的である。空文字列の要約は左右どちらから結合しても値を変えない。構築時に不変条件が成立し、更新時も変更した葉から祖先を計算し直せば保たれる。区間取得では、対象区間を過不足なく覆う節点を元の順序で結合するので、その部分文字列の正しい要約を得られる。

次に判定を考える。回文なら元の文字列と逆順の文字列が等しいため、すべての基数で f(T)=r(T)f(T)=r(T) となり、必ず Yes を返す。一つでも不一致なら回文ではない。残る誤りは、回文でない文字列を衝突により Yes と判定する場合だけである。

この誤りを評価するため、入力全体は乱数選択と独立に固定されていると仮定する。法を素数 p>26p>26 に固定し、基数 BB を 1,…,p−11,\ldots,p-1 から一様に選ぶ。長さ mm の固定された非回文について、法を取る前の f(T)−r(T)f(T)-r(T) を基数の変数に関する多項式とみなす。左右対称の位置に異なる文字があるので係数の少なくとも一つは非零であり、文字の値が1から26、p>26p>26 だから法 pp でも非零である。次数は高々 m−1m-1。体上の非零多項式の根は次数以下なので、衝突確率は高々 εm=min⁡(1,(m−1)/(p−1))\varepsilon_m=\min(1,(m-1)/(p-1)) となる。

同じ法に対して kk 個の基数を独立に一様選択し、すべてのハッシュが一致することを要求すれば、この一回の誤判定確率は高々 εmk\varepsilon_m^k。操作列も固定されているため、更新後に比較する部分文字列も乱数に依存しない。判定は高々 QQ 回なので、全体で一度でも誤る確率は和の上界から高々

Q(min⁡(1,N−1p−1))kQ\left(\min\left(1,\frac{N-1}{p-1}\right)\right)^k

である。異なる判定の間の独立性は不要であり、基数間の独立性により一回の上界を累乗している。

例えば p=109+7p=10^9+7、k=4k=4 なら、本問の上限 N≤106,Q≤105N\leq 10^6,Q\leq 10^5 で全体の上界は 10−710^{-7} 未満になる。これは上の乱択の仮定に基づく評価であり、ハッシュ一致が文字列一致を保証するわけではない。固定した基数を複製しても独立な判定は増えず、この評価は使えない。

実装上の注意

  • 結合は常に「左の区間、右の区間」の順にする。反復型の区間取得で左右二つの集約値を使う場合、左側へ見つけた節点は左側の集約値の後ろへ、右側へ見つけた節点は右側の集約値の前へ結合し、最後に左側と右側を結合する。
  • 入力の位置だけを0始まりへ直す。更新位置は x−1x-1、判定区間は [L−1,R)[L-1,R) とし、右端の RR をさらに減らさない。
  • 空区間や余った葉は (0,0,1)(0,0,1)。基数冪を0にすると単位元にならない。同じ文字への更新も葉を置き換える通常処理でよく、先頭・末尾の更新にも例外は要らない。
  • 乱数は開始時に選び、その後は各基数を全区間で固定する。ここでは素数 p=1000000007p=1000000007 に対して4個の基数を独立に一様選択する。同じ基数の順方向・逆方向は一組の比較であり、独立な二つのハッシュとは数えない。
  • 積を取ってから法を取る。上の法では積と加算の途中値は符号付き64 bit整数に収まるが、32 bit整数には収まらない。C++なら乗算前に64 bitへ変換する。法を大きく変更する場合は、その積に必要な幅も再評価する。

復習の核

  • 回文の真偽を直接結合できないとき、両向きに読んだ列の一致へ戻る。
  • 連結の式は暗記せず、文字を足した側の長さだけ桁を移す。順方向では右の長さ、逆方向では左の長さを使う。
  • 答えのためのハッシュと、次の結合のための基数冪を一緒に残す。空文字列の基数冪は1である。
  • ハッシュの合成は正確でも、一致から元の列の一致へ戻る推論には衝突が残る。乱択の仮定と比較回数まで含めて誤りを評価する。

計算量と制約

時間

基数の個数を kk とすると、葉の準備と木の構築に O(kN)O(kN)、各更新・区間取得に O(klog⁡(N+1))O(k\log(N+1))、取得後の比較に O(k)O(k) かかる。全体は O(k(N+Qlog⁡(N+1)))O(k(N+Q\log(N+1))) 時間。ここでは k=4k=4 を固定し、法上の演算を定数時間とするので、O(N+Qlog⁡(N+1))O(N+Q\log(N+1)) と書ける。

空間

各節点に kk 組の三つの値を持ち、節点数は O(N)O(N) なので、木が O(kN)O(kN)。入力文字列と区間取得の作業領域を含めても O(kN)O(kN) で、k=4k=4 を固定すれば O(N)O(N)。操作は入力順に処理でき、全クエリを保存する必要はない。

制約との対応

1≤N≤1061\leq N\leq 10^6、1≤Q≤1051\leq Q\leq 10^5。一点更新の位置は 1≤x≤N1\leq x\leq N、判定区間は 1≤L≤R≤N1\leq L\leq R\leq N である。長い区間でも全走査せず、高々 O(log⁡(N+1))O(\log(N+1)) 個の節点の結合で処理する。N=1N=1 でも木の構築・一回の操作は定数時間で済む。文字が英小文字なので、1から26への写像は選んだ法上で単射になる。初期化時は一文字ずつ更新して O(Nlog⁡N)O(N\log N) にせず、葉をまとめて置いてから下から構築する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Palindrome Query の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間monoid要約

主題
  • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
追加で学ぶ技能
    なし
    既習技能
    • 列・文字列のrolling fingerprint: 順序を保つprefix hashと連結則を設計し、部分列のhash差やLCP二分探索で列の一致を比較する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 区間monoid要約

    補助タグ: 列・文字列のrolling fingerprint

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

    学習の位置

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

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

    先に読む単元:

    • 列・文字列のrolling fingerprint — 順序を保つprefix hashと連結則を設計し、部分列のhash差やLCP二分探索で列の一致を比較する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題