ABC 308 G — Minimum Xor Pair Query

考察

すべての組のXORを持つと、一つの整数を追加するたびに多数の候補が増える。ところが、昇順で隣り合わない二値は、間の値を使ってより小さいXORへ置き換えられる。従って隣接対だけを候補にでき、一要素の挿入・削除で変わる数本の対を更新すればよい。

動かす前に、静止した集合で候補を減らす

整数の追加、一個の削除、異なる二要素のXORの最小値取得を処理する。同じ値が二個あれば、それらを選べるので答えは0である。クエリ数は最大30万。現在の要素数を nn とすると、全対の確認に O(n2)O(n^2)、全対を保存しても追加のたびに O(n)O(n) 個の更新が必要になる。

まず更新を忘れ、一つの集合で最小値を速く求められないか考える。XORが小さいためには、高い桁から多くのビットが一致している必要がある。整数を昇順にすると、同じ上位ビットを持つ数は固まって並ぶ。この並びに候補削減の手がかりがある。

独自例 (2,3,10,11)(2,3,10,11) の全対を比べる。

対XOR昇順で隣接
2と31はい
2と108いいえ
2と119いいえ
3と109はい
3と118いいえ
10と111はい

最小値1は隣接対から得られた。ただし、「数値の差が小さければXORも小さい」とは言えない。7と8は差1でもXORが15、5と7は差2でもXORが2である。必要なのは近さの直感ではなく、非隣接対を除外できる論証だ。

間の値は、どちらかの端と上位ビットがそろう

相異なる三値 x<y<zx<y<z を取る。x,zx,z が初めて異なる最上位の桁を、下から0始まりで kk 桁目とする。この桁では xx が0、zz が1なので、

x⊕z≥2kx\oplus z\geq2^k

である。それより上位の共通部分を固定した整数は、ある連続区間をなす。両端がその区間内にあり、その間の yy も区間を出ないため、yy の上位部分も同じである。

yy の kk 桁目は0か1のどちらかだ。0なら xx と、1なら zz と、kk 桁目まで一致する。従って必ず、

min⁡(x⊕y, y⊕z)<2k≤x⊕z\min(x\oplus y,\ y\oplus z)<2^k\leq x\oplus z

となる。例えば 3=011,5=101,6=1103=011,5=101,6=110 では、4の位で5と6がそろい、5⊕6=3<3⊕6=55\oplus6=3<3\oplus6=5 となる。

値がすべて異なるなら、非隣接対には必ず中間値があり、その対よりよい候補が見つかる。よって最小対は隣接する。重複があるなら、等しい値が隣り合い、下界0を達成する。この二つを合わせると、昇順の列 a1≤⋯≤ana_1\leq\cdots\leq a_n について、

min⁡i<j(ai⊕aj)=min⁡1≤i<n(ai⊕ai+1)\min_{i<j}(a_i\oplus a_j) =\min_{1\leq i<n}(a_i\oplus a_{i+1})

が得られる。候補は n−1n-1 個に減った。

値の列と、隣接対の値を別々に保つ

次の二つの多重集合を空で初期化する。

  • SS:今ある整数を、同じ値の個数も含めて昇順に保つ。
  • CC:SS の隣接対一つにつき、そのXORを一個保つ。

答えは CC の最小値である。SS だけでは、ある隣接対が消えた後に「次に小さい候補」を探し直す必要があるので、候補自体も順序付きで保つ。

挿入する位置の直前を ll、直後を rr とする。xx を間に入れると、隣接関係の変化は次だけである。

変更前: … l ───── r …
変更後: … l ─ x ─ r …

両隣があれば l⊕rl\oplus r を一個消す。左隣があれば l⊕xl\oplus x を、右隣があれば x⊕rx\oplus r を一個ずつ加える。先頭や末尾への挿入では、存在する側だけを扱う。

削除では、実際に消す一要素を探し、その左右を消す前に取得する。l⊕xl\oplus x と x⊕rx\oplus r をそれぞれ一個消し、両隣があれば l⊕rl\oplus r を一個加え、最後に xx 自身を一個消す。

先ほどの例で、3の追加と削除を追う。

操作後の SSCC を昇順に表示答え
(2,10,11)(2,10,11)(1,8)(1,8)1
3を追加:(2,3,10,11)(2,3,10,11)(1,1,9)(1,1,9)1
3を削除:(2,10,11)(2,10,11)(1,8)(1,8)1

3の削除で消すのは、対 (2,3)(2,3) の1と、対 (3,10)(3,10) の9である。別の対 (10,11)(10,11) の1は残す。元の整数が相異なっていても、候補のXORには重複が生まれるので、候補側も多重集合でなければならない。

順序付き多重集合なら、挿入位置の探索と定数個の挿入・削除を各 O(log⁡Q)O(\log Q) で行える。クエリ3では先頭を見るだけでよい。

典型の発動条件

全対の最適化を、間の要素との交換で隣接対へ絞る

集合から二要素を選ぶ問題では、最適化の対象をすべて動的に管理する前に、静的な場合の候補削減を考える。順序を入れた三値 x<y<zx<y<z について、両端の対を内側の対へ置き換えて悪化しないと示せれば、添字の間隔を狭めて隣接対へ到達できる。

本問は最高相違ビットで真に改善することを示した。絶対差の最小化でも同じ方針が使える。一方、数値順を導入しただけでは成立しない。たとえば積を最大化する問題で、全候補を隣接対に限定する根拠にはならない。どの対をどの対へ交換できるかが、データ構造を選ぶ前の数学的な課題である。

一次元の隣接関係は、一要素の更新に対して局所的に変わる

隣接対を一本の辺と見ると、挿入は一辺を二辺へ分割し、削除は二辺を一辺へつなぎ直す操作になる。各辺の情報を別の集合へ入れておけば、隣接差の最大値、隣接コストの総和などにも使える。和なら増減する値を足し引きするだけでよく、最小・最大なら候補の多重集合を使う。

この更新方法と「全対の答えが隣接対から得られる」という性質は別である。前者は順序の局所性、後者は目的関数の性質だ。本問は両方が成り立つため、数学的な候補削減と高速な動的更新を接続できた。

問題固有の要素

XORの比較では、下位の桁の値を足し合わせるより、最初に異なる上位の一桁で大小の境界を作るとよい。本問では「両端で異なる桁は、中間値ではどちらかと一致する」という二択が、非隣接対を除外する鍵になる。Binary Trieで共通する上位ビットごとに分ける見方も近いが、本問の全体最小値には隣接候補を保つ方が簡潔である。

正当性

重複値があれば、昇順で等しい値が隣接してXORが0になり、全対の最小値を達成する。値がすべて相異なる場合、非隣接の二値には厳密にその間の値がある。最高相違ビットの議論により中間値と片端とのXORは両端のXORより小さいので、非隣接対は最小対になれない。従って全隣接対を調べれば答えが得られる。

空集合では隣接対もなく、CC はそのXORを正しく保つ。挿入では、新しい要素の両隣をつなぐ対だけが消え、新しい要素と各隣との対だけが増える。削除ではその逆になる。端に要素がない場合の処理を省き、各候補を個数単位で増減することで、更新後も CC は現在の全隣接対のXORと多重度を含めて一致する。

よって各クエリ3で CC の最小値を返せば、求める全対の最小XORになる。クエリ3には二要素以上あることが保証され、最小値の参照先も存在する。

実装上の注意

  • C++では multiset を二つ使える。一個削除するときは find したイテレータを erase へ渡す。erase(value) は同じ値を全部消してしまう。
  • 重複値の隣接関係は「その値より小さい/大きいもの」で求めず、実際に挿入・削除する位置の直前・直後で求める。等しい値も隣になり得る。
  • prev(begin()) や next(end()) は取らない。削除対象の隣と値は、対象を消す前に確保する。
  • 要素数が nn なら候補数は max⁡(n−1,0)\max(n-1,0)。一個から空へ戻る操作でも、この対応を保つ。候補の個数だけが合っていても値が正しいとは限らないので、小例では候補全体を追う。
  • XORは 2302^{30} 未満に収まる。値の範囲と、別の問題で隣接コストの和を持つ場合の整数幅は分けて考える。

復習の核

  • 動的な全対問題は、まず静的な一集合で候補を減らす。
  • 隣接だけでよい理由を、三値の中間要素と最高相違ビットから説明する。
  • 一要素の挿入・削除では、消える隣接対と生まれる隣接対を先に描く。
  • 値の個数と、候補値の個数を別々に保つ。同じXORでも対が違えば残す。

計算量と制約

時間

各挿入・削除は位置の探索と定数個の多重集合操作からなり、O(log⁡Q)O(\log Q) 時間。最小値取得は O(1)O(1)、入出力を含め全 QQ クエリで O(Qlog⁡Q)O(Q\log Q) 時間となる。

空間

元の整数は最大 QQ 個、隣接XORはそれより一個少ない。クエリを読みながら処理すれば、二つの多重集合を含む全空間は O(Q)O(Q) である。

制約との対応

Q≤3×105Q\leq3\times10^5、0≤x<2300\leq x<2^{30}。削除対象の存在と、最小値取得時に二要素以上あることが保証される。対を二次個保存せず、最大 Q−1Q-1 個の隣接候補に絞ることで、このクエリ数を処理できる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: ordered set・multisetの動的順序管理

主題
  • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: ordered set・multisetの動的順序管理

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

      学習の位置

      体系上の位置: ordered set・multisetの動的順序管理

      • 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題