競プロ用ライブラリを作る Advent Calendar 2024の7日目です.
Mo's Algorithmって?
巡回セールスマン問題 (の巡回しないバージョン) の近似解を用いた効率的にクエリを捌くテクニックです.
要件定義が難しいので例題を出します.
長さ$N$の数列$A_1, A_2, ..., A_N$があります.
$Q$個質問があります. $i$番目の質問は以下のようになります.
- $A_{L_i}, A_{L_i+1}, A_{L_i+2}, ..., A_{R_i}$には何種類の数が含まれていますか?
全ての質問に答えてください.
制約
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^5$
- $1 \le Q \le 10^5$
- $1 \le L_i \le R_i \le N$
Mo's Algorithmではこの問題に$O(N\sqrt Q + Q \log Q)$のような計算量で求められます.
仕組み
以下, 各クエリでの正解を$f(L, R)$と書くことにします.
とりあえず例題の$Q = 1$の場合を考えます. 解き方は色々あると思いますが, ここでは「配列で値ごとに個数を管理 + 1つ以上ある値が何個あるかも同時に集計」という方法にします.
この方法ですが, $f(L, R)$を求める時に使った配列は$f(L\pm1,R)$や$f(L,R\pm1)$などの計算に使いまわせます. 区間の大部分が重複しているので, ちょっとの変更で移り変われます.
Mo's Algorithmはこのような計算結果の使いまわしでクエリに答えるテクニックです.
$f(L_1,R_1)$の結果から$f(L_2,R_2)$の結果を計算するには$O(\lvert L_1-L_2\rvert+\lvert R_1-R_2\rvert)$くらいのコストがかかります. コストをなるべく減らしたいので, コストが小さくなるようにクエリを並べ替えて, $f(L_{a_1},R_{a_1})\to f(L_{a_2},R_{a_2})\to...\to f(L_{a_N},R_{a_N})$というように使いまわしのリレーを行います.
問題はどう並べ替えればいいか, です. 平方分割などをする方法が有名らしいですが, ここではHilbert曲線を使った方法を紹介します.
Hilbert曲線とはこういう曲線のことです. 赤い点からスタートして無限に伸びてます.
この曲線をどう使うかというと, まず問題を言い換えます. 各クエリは$(L, R)$という平面上の点に対応していて, 問題はできるだけ短い距離でクエリの点を全部通りたいということです. この解決法として, 各クエリがHilbert曲線のどこに乗っているか見て, その順にクエリを見ることにします.
Hilbert曲線上で近い点は平面上でも近いところにあるので, いい感じに計算量が削減できます.
計算量の見積もりは大変ですが, 頑張ると$O(N\sqrt Q)$くらいだと分かり, クエリをソートした分を含めると$O(N\sqrt Q + Q \log Q)$です.
実装
答えを入れる配列は適当な順番で埋まっていきます. どの順番でも埋められるようにRust 1.82.0で安定化したばかりのBox::new_uninit_slice / Box::assume_init を使いました. 計算中にpanicしてもデストラクタが動くように工夫してます.
まとめ
いかがでしたか?
明日は数学をします.