ABC 367 F — Rearrange Query

考察

並べ替えた後に一致するかどうかは、各値が何個ずつあるかで決まる。この個数をすべて比較する代わりに、値ごとに決めた乱数を出現回数だけ足し、その和を「指紋」として比較する。和なら順序に依存せず、累積和から区間の指紋を高速に取り出せる。

まず、各クエリで両区間をソートして比較すれば正しく判定できる。しかし、長い区間を繰り返し比較する場合は全体で O(QNlog⁡N)O(QN\log N) かかり、N,Q≤2×105N,Q\leq 2\times 10^5 には間に合わない。必要なのは順序を捨てた多重集合、すなわち各値の出現回数の一致である。値ごとの個数の累積和をすべて用意すると、今度は O(N2)O(N^2) の前処理・記憶量が必要になる。

そこで個数の情報を一つの和へ縮めたい。ただし通常の要素和では、独自例 {1,1,4}\{1,1,4\} と {1,2,3}\{1,2,3\} がともに6となり、長さも和も等しいのに区別できない。各値へランダムな重みを割り当てれば、このような決まった相殺を避けられる。

ここでは素数 p>Np>N を固定する。Fp\mathbb F_p は、0,1,…,p−10,1,\ldots,p-1 を法 pp で加減乗算する体である。値 v=1,…,Nv=1,\ldots,N ごとに、Fp\mathbb F_p から独立一様に乱数 h(v)h(v) を一度だけ選ぶ。同じ値には、出現位置によらず、配列 A,BA,B の両方で同じ乱数を使う。多重集合 SS での値 vv の個数を cv(S)c_v(S) とし、指紋を

H(S)=∑v=1Ncv(S)h(v)(modp)H(S)=\sum_{v=1}^{N} c_v(S)h(v)\pmod p

と定める。個数を係数として残すので、同じ値が二度出れば 2h(v)2h(v) が寄与する。XORでは h(v)XORh(v)=0h(v)\mathbin{\mathrm{XOR}}h(v)=0 となり、異なる値 x,yx,y に対する {x,x}\{x,x\} と {y,y}\{y,y\} が常に同じ0へ潰れるため、本問の多重集合には使えない。

入力に合わせ、配列も区間も1始まりの閉区間で扱う。最初の ii 要素の指紋を PA[i],PB[i]P_A[i],P_B[i] とすると、初期値と更新は

PA[0]=PB[0]=0,PA[i]=(PA[i−1]+h(Ai)) mod p,PB[i]=(PB[i−1]+h(Bi)) mod p\begin{aligned} P_A[0]&=P_B[0]=0,\\ P_A[i]&=(P_A[i-1]+h(A_i))\bmod p,\\ P_B[i]&=(P_B[i-1]+h(B_i))\bmod p \end{aligned}

である。i=1,…,Ni=1,\ldots,N の順に構築すると、区間 Al,…,ArA_l,\ldots,A_r の指紋は (PA[r]−PA[l−1]) mod p(P_A[r]-P_A[l-1])\bmod p となる。BL,…,BRB_L,\ldots,B_R も同様に求められる。

各クエリではまず r−l+1r-l+1 と R−L+1R-L+1 を比較し、長さが違えば No とする。同じ長さなら指紋を比較し、不一致なら No、一致なら Yes を返す。異なる多重集合が偶然同じ指紋になることを衝突と呼ぶ。後の証明で誤り確率を評価し、ここでは p=261−1p=2^{61}-1、互いに独立な乱数表2組を採用する。各組で累積和を作り、両組の指紋が一致したときだけ Yes とする。

典型の発動条件

Zobrist型multiset hashing

順序を無視し、重複回数を保って一致判定したいときに、値ごとの乱数を加算する指紋が候補になる。素数の法を各多重集合の大きさより大きくし、整数として異なる個数が法を取っても消えないことを確認する。

例えば同じ値 pp 個と空集合の指紋は常に等しい。法の条件を外した失敗は、乱数表を増やしても解消しない。

hash prefix sum

配列が静的で、区間の情報を加法的な指紋へ写せたときは、累積和の差で1組あたり O(1)O(1) で取り出せる。配列に更新がある場合は、累積和をそのまま使い回せず、別途区間和を維持する構造が必要になる。

問題固有の要素

本問では値域が 1,…,N1,\ldots,N なので、乱数表は配列で持てる。また各区間の長さは高々 NN であり、p>Np>N と選ぶだけで、後述の頻度差が体上でも非零になる条件を満たせる。

持ち帰る視点は、比較したい情報に指紋の演算を合わせることである。並び順を比べる指紋では位置の情報を残し、多重集合を比べる本問では加算の可換性で順序を捨てる。

正当性

以下では、入力の両配列と全クエリは乱数を選ぶ前に固定されているとする。確率はこの固定入力に対する乱数表の選び方について評価する。

累積和の差では区間より前の寄与がすべて打ち消され、区間内の各値がその出現回数だけ残る。従って得られる値は定義した指紋に等しい。二つの区間が同じ多重集合なら、すべての出現回数が一致するので、どの乱数表でも指紋は一致する。長さも一致するため、正しい答えが Yes の場合に No を返すことはない。

異なる多重集合 S,TS,T の1比較を考える。値 vv の頻度差を Δv=cv(S)−cv(T)\Delta_v=c_v(S)-c_v(T) とすると、整数として非零の Δu\Delta_u を持つ値 uu がある。各区間の長さは高々 NN なので 0<∣Δu∣≤N<p0<|\Delta_u|\leq N<p であり、Δu\Delta_u は Fp\mathbb F_p でも非零である。衝突条件は

Δuh(u)+∑v≠uΔvh(v)=0in Fp\Delta_u h(u)+\sum_{v\ne u}\Delta_v h(v)=0\quad\text{in }\mathbb F_p

となる。h(u)h(u) 以外の乱数をすべて固定すると、和の部分は定数になる。体では非零の Δu\Delta_u で割れるので、この等式を満たす h(u)h(u) はただ一つである。残した h(u)h(u) は他の乱数と独立で、pp 個の体元から一様に選ばれるため、条件付きの衝突確率は 1/p1/p。他の乱数の選び方について平均しても 1/p1/p となる。長さの違う区間は先に弾くので、1クエリの誤り確率は高々 1/p1/p である。

互いに独立な乱数表を tt 組使い、すべての指紋が一致したときだけ Yes とすれば、異なる多重集合が全組で衝突する確率は 1/pt1/p^t となる。全 QQ クエリのうち一つでも誤る確率は、事象の和の上界(union bound)により

Pr⁡(どこかのクエリで誤る)≤Qpt\Pr(\text{どこかのクエリで誤る})\leq \frac{Q}{p^t}

で抑えられる。同じ乱数表を全クエリで共有しているため、クエリ間の衝突は独立とは限らないが、union boundにその独立性は不要である。一方、1/pt1/p^t への減少には、乱数表同士の独立性が必要になる。

本問の上限 Q≤2×105Q\leq 2\times 10^5 に対し、p=261−1p=2^{61}-1 なら1組でも全クエリの誤り確率は Q/p<8.7×10−14Q/p<8.7\times 10^{-14}。採用した2組では Q/p2<3.8×10−32Q/p^2<3.8\times 10^{-32} となる。この評価は、公式解説の加算ハッシュを、値ごと・組ごとに独立一様な体元を使うモデルへ具体化したものである。

実装上の注意

  • 乱数は0を含む 0,…,p−10,\ldots,p-1 から選ぶ。一様な64 bit乱数の下位61 bitを取り、値が pp の場合だけ引き直せば、この範囲で一様になる。単に64 bit乱数の剰余を取ると分布が偏る。実装には疑似乱数生成器を使うが、上の確率保証は独立一様な乱数のモデルに対するものと区別する。入力値から決定的に重みを作るだけで、同じ保証が得られるわけではない。
  • 2組目は新たに乱数を生成する。1組目をそのまま複製したり、各重みを同じ非零定数倍にしたりしても、衝突が同時に起きるので誤り確率は二乗にならない。
  • 累積和の各値は毎回 0,…,p−10,\ldots,p-1 に正規化する。二つの値の加算は 2p−2<2622p-2<2^{62}、区間差を非負にする P[r]+p−P[l−1]P[r]+p-P[l-1] は高々 2p−1<2622p-1<2^{62} なので、符号なし64 bit整数で安全に計算できる。この方式は乗算を使わず、128 bit整数は不要である。区間差も法 pp で正規化してから比較する。
  • 法 2W2^W の unsigned 加算へ置き換えると、体上の証明は使えない。異なる値 x,yx,y の独自例 {x,x},{y,y}\{x,x\},\{y,y\} では、衝突条件は 2(h(x)−h(y))=0(mod2W)2(h(x)-h(y))=0\pmod{2^W}。独立一様な WW bit乱数で W≥1W\geq 1 のとき、差が 00 または 2W−12^{W-1} なら衝突し、その確率は 2/2W=2−(W−1)2/2^W=2^{-(W-1)} である。常に0になるXORの例とも、素数体での 1/p1/p とも区別する。本解説の手順は素数の法に統一する。
  • l=1l=1 または L=1L=1 では先頭の累積和0を使う。長さ1の区間、同じ値ばかりの区間も特別扱いは不要である。クエリを順次処理して出力すれば、全クエリを保存する必要はない。

復習の核

並べ替えで同一視する情報は「各値の個数」であり、それを乱数との線形和へ写すと区間の累積和が使える。復習では、非零の頻度差が法を取っても消えない理由と、他の乱数を固定すると衝突させる体元が一つになる理由を再現する。さらに、1比較の上界に全比較回数を掛け、独立な乱数表を増やす費用と効果まで評価する。

計算量と制約

時間

乱数表 tt 組の生成と累積和の構築に期待 O(tN)O(tN)、全クエリの比較・出力に O(tQ)O(tQ)、合計で期待 O(t(N+Q))O(t(N+Q))。期待値なのは一様乱数生成の引き直しによるもので、1回の採用確率は 1−2−611-2^{-61} である。固定した t=2t=2 では期待 O(N+Q)O(N+Q) となる。

空間

値ごとの乱数表と両配列の累積和が各組で O(N)O(N)、入力配列も含めて O(tN)O(tN)。クエリを保存しなければ O(Q)O(Q) の領域は不要で、t=2t=2 では O(N)O(N) である。

制約との対応

公式制約は 1≤N,Q≤2×1051\leq N,Q\leq 2\times 10^5、1≤Ai,Bi≤N1\leq A_i,B_i\leq N、1≤li≤ri≤N1\leq l_i\leq r_i\leq N、1≤Li≤Ri≤N1\leq L_i\leq R_i\leq N。実行時間制限は2秒、メモリ制限は1024 MiBである。p=261−1>Np=2^{61}-1>N なので、頻度差が法を取ると0になる事態を避けられる。2組の乱数表と両配列の累積和は計6本の長さ N+1N+1 の64 bit整数配列で持て、上限でも約9.6 MBである。線形な前処理と1クエリあたり定数回の演算で、長い区間を繰り返し走査する必要がない。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 乱択代数fingerprint

主題
  • 乱択代数fingerprint: multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 乱択代数fingerprint

    補助タグ: 乱択・Monte Carloアルゴリズム

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

    学習の位置

    体系上の位置: 乱択代数fingerprint

    • multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題