考察
すべての組のXORを持つと、一つの整数を追加するたびに多数の候補が増える。ところが、昇順で隣り合わない二値は、間の値を使ってより小さいXORへ置き換えられる。従って隣接対だけを候補にでき、一要素の挿入・削除で変わる数本の対を更新すればよい。
動かす前に、静止した集合で候補を減らす
整数の追加、一個の削除、異なる二要素のXORの最小値取得を処理する。同じ値が二個あれば、それらを選べるので答えは0である。クエリ数は最大30万。現在の要素数を とすると、全対の確認に 、全対を保存しても追加のたびに 個の更新が必要になる。
まず更新を忘れ、一つの集合で最小値を速く求められないか考える。XORが小さいためには、高い桁から多くのビットが一致している必要がある。整数を昇順にすると、同じ上位ビットを持つ数は固まって並ぶ。この並びに候補削減の手がかりがある。
独自例 の全対を比べる。
最小値1は隣接対から得られた。ただし、「数値の差が小さければXORも小さい」とは言えない。7と8は差1でもXORが15、5と7は差2でもXORが2である。必要なのは近さの直感ではなく、非隣接対を除外できる論証だ。
間の値は、どちらかの端と上位ビットがそろう
相異なる三値 を取る。 が初めて異なる最上位の桁を、下から0始まりで 桁目とする。この桁では が0、 が1なので、
である。それより上位の共通部分を固定した整数は、ある連続区間をなす。両端がその区間内にあり、その間の も区間を出ないため、 の上位部分も同じである。
の 桁目は0か1のどちらかだ。0なら と、1なら と、 桁目まで一致する。従って必ず、
となる。例えば では、4の位で5と6がそろい、 となる。
値がすべて異なるなら、非隣接対には必ず中間値があり、その対よりよい候補が見つかる。よって最小対は隣接する。重複があるなら、等しい値が隣り合い、下界0を達成する。この二つを合わせると、昇順の列 について、
が得られる。候補は 個に減った。
値の列と、隣接対の値を別々に保つ
次の二つの多重集合を空で初期化する。
- :今ある整数を、同じ値の個数も含めて昇順に保つ。
- : の隣接対一つにつき、そのXORを一個保つ。
答えは の最小値である。 だけでは、ある隣接対が消えた後に「次に小さい候補」を探し直す必要があるので、候補自体も順序付きで保つ。
挿入する位置の直前を 、直後を とする。 を間に入れると、隣接関係の変化は次だけである。
変更前: … l ───── r …
変更後: … l ─ x ─ r …
両隣があれば を一個消す。左隣があれば を、右隣があれば を一個ずつ加える。先頭や末尾への挿入では、存在する側だけを扱う。
削除では、実際に消す一要素を探し、その左右を消す前に取得する。 と をそれぞれ一個消し、両隣があれば を一個加え、最後に 自身を一個消す。
先ほどの例で、3の追加と削除を追う。
3の削除で消すのは、対 の1と、対 の9である。別の対 の1は残す。元の整数が相異なっていても、候補のXORには重複が生まれるので、候補側も多重集合でなければならない。
順序付き多重集合なら、挿入位置の探索と定数個の挿入・削除を各 で行える。クエリ3では先頭を見るだけでよい。
典型の発動条件
全対の最適化を、間の要素との交換で隣接対へ絞る
集合から二要素を選ぶ問題では、最適化の対象をすべて動的に管理する前に、静的な場合の候補削減を考える。順序を入れた三値 について、両端の対を内側の対へ置き換えて悪化しないと示せれば、添字の間隔を狭めて隣接対へ到達できる。
本問は最高相違ビットで真に改善することを示した。絶対差の最小化でも同じ方針が使える。一方、数値順を導入しただけでは成立しない。たとえば積を最大化する問題で、全候補を隣接対に限定する根拠にはならない。どの対をどの対へ交換できるかが、データ構造を選ぶ前の数学的な課題である。
一次元の隣接関係は、一要素の更新に対して局所的に変わる
隣接対を一本の辺と見ると、挿入は一辺を二辺へ分割し、削除は二辺を一辺へつなぎ直す操作になる。各辺の情報を別の集合へ入れておけば、隣接差の最大値、隣接コストの総和などにも使える。和なら増減する値を足し引きするだけでよく、最小・最大なら候補の多重集合を使う。
この更新方法と「全対の答えが隣接対から得られる」という性質は別である。前者は順序の局所性、後者は目的関数の性質だ。本問は両方が成り立つため、数学的な候補削減と高速な動的更新を接続できた。
問題固有の要素
XORの比較では、下位の桁の値を足し合わせるより、最初に異なる上位の一桁で大小の境界を作るとよい。本問では「両端で異なる桁は、中間値ではどちらかと一致する」という二択が、非隣接対を除外する鍵になる。Binary Trieで共通する上位ビットごとに分ける見方も近いが、本問の全体最小値には隣接候補を保つ方が簡潔である。
正当性
重複値があれば、昇順で等しい値が隣接してXORが0になり、全対の最小値を達成する。値がすべて相異なる場合、非隣接の二値には厳密にその間の値がある。最高相違ビットの議論により中間値と片端とのXORは両端のXORより小さいので、非隣接対は最小対になれない。従って全隣接対を調べれば答えが得られる。
空集合では隣接対もなく、 はそのXORを正しく保つ。挿入では、新しい要素の両隣をつなぐ対だけが消え、新しい要素と各隣との対だけが増える。削除ではその逆になる。端に要素がない場合の処理を省き、各候補を個数単位で増減することで、更新後も は現在の全隣接対のXORと多重度を含めて一致する。
よって各クエリ3で の最小値を返せば、求める全対の最小XORになる。クエリ3には二要素以上あることが保証され、最小値の参照先も存在する。
実装上の注意
- C++では
multiset を二つ使える。一個削除するときは find したイテレータを erase へ渡す。erase(value) は同じ値を全部消してしまう。
- 重複値の隣接関係は「その値より小さい/大きいもの」で求めず、実際に挿入・削除する位置の直前・直後で求める。等しい値も隣になり得る。
prev(begin()) や next(end()) は取らない。削除対象の隣と値は、対象を消す前に確保する。
- 要素数が なら候補数は 。一個から空へ戻る操作でも、この対応を保つ。候補の個数だけが合っていても値が正しいとは限らないので、小例では候補全体を追う。
- XORは 未満に収まる。値の範囲と、別の問題で隣接コストの和を持つ場合の整数幅は分けて考える。
復習の核
- 動的な全対問題は、まず静的な一集合で候補を減らす。
- 隣接だけでよい理由を、三値の中間要素と最高相違ビットから説明する。
- 一要素の挿入・削除では、消える隣接対と生まれる隣接対を先に描く。
- 値の個数と、候補値の個数を別々に保つ。同じXORでも対が違えば残す。
計算量と制約
時間
各挿入・削除は位置の探索と定数個の多重集合操作からなり、 時間。最小値取得は 、入出力を含め全 クエリで 時間となる。
空間
元の整数は最大 個、隣接XORはそれより一個少ない。クエリを読みながら処理すれば、二つの多重集合を含む全空間は である。
制約との対応
、。削除対象の存在と、最小値取得時に二要素以上あることが保証される。対を二次個保存せず、最大 個の隣接候補に絞ることで、このクエリ数を処理できる。
出典