Mo's Algorithm
もうです
Mo's Algorithmとは？
以下のような条件を満たす数列上の区間に対するクエリを高速に求められるアルゴリズムである。
数列に対する更新がない
ある区間$ [l:r] に対するクエリの答えが分かっているとき、左または右端のいずれかを$ 1 要素分いずれの方向にずらしてもその答えを簡単に求められる($ [l+1:r], [l-1:r], [l:r+1], [l:r-1] のいずれも簡単に求められる)。
時間計算量は$ \Omicron(\alpha N \sqrt{Q})となる。ただし$ \alphaは区間の端を$ 1つずらすときの計算量である。
例題
長さ$ Nの数列$ Aが与えられる。以下のようなクエリに$ Q件答えよ。
各クエリでは$ l, rが与えられる。$ A_l, A_{l+1}, \ldots, A_rのうちで$ 1度だけ出現する値の種類を答えよ。
制約 $ 1 \leq N, Q, A_i \leq 10^5
しかし、ある区間の答えがわかっていればその区間の端を$ 1つだけ伸ばす、縮めることは出来る(全値のカウント用の配列と、現在の答えを持っておけばよい)。
ここで、クエリを以下のようにソートする。
バケットサイズを$ Mとする。
クエリ区間の左端を幅$ Mのブロックごとに分ける。左端が同じブロックに入るクエリ同士は右端を見てソートする。
この時、右端は全部昇順でも間に合うが、$ l / Mを小数点以下切り捨てたときに奇数のときだけ降順、にするとより速い。
この状態で後は愚直にクエリを先頭から見て左右の差分だけずらす処理を書く。
ここで、$ M = \frac{N}{\sqrt{Q}}とすることで時間計算量が$ \Omicron(\alpha N \sqrt{Q})となる。
どうして……？
これで時間計算量が$ \Omicron(\alpha N \sqrt{Q})になるのはちょっとよくわからないと思う(というか普通にわからない)ので、以下に解析の流れを置いておく。
各クエリについて$ \Omicron(S)かかるとする。この時時間計算量は$ \Omicron(Q(S))である。$ Sをより厳密に求める。
各クエリの操作を以下のように分解する。
左端を移動する。左端はブロック単位でまとめられておりブロック幅は$ \frac{N}{\sqrt{Q}}であるので、最悪のケースにおいてはブロックの端から端まで移動することとなり、この操作は$ \Omicron(Q α \frac{N}{\sqrt{Q}} = \alpha \frac{NQ \sqrt Q}{\sqrt Q^2} = \alpha N \sqrt Q)
右端を移動する。左端のブロックごとに右端の移動量は最大$ Nなので$ \Omicron(N \times \alpha N \div \frac{N}{\sqrt Q} = \alpha N \sqrt Q)
よって、総じて$ \Omicron(\alpha N \sqrt Q)となる。
補足
Nyaan さんのライブラリによると$ \frac{N \sqrt 3}{\sqrt{2Q}}をバケットサイズとして選ぶのが最も高速らしい。 左端の移動回数は$ \Omicron(\alpha Q \frac{N \sqrt 3}{\sqrt{2Q}} = \alpha \frac {QN \sqrt{3Q}}{2Q} = \frac{\sqrt 3}{2} \alpha N \sqrt Q)となり、額面では$ M = \frac{N}{\sqrt Q}より$ 1.15倍ほど高速になる。
右端の移動回数は$ \Omicron(\alpha \frac{N^2 \sqrt{2Q}}{N \sqrt 3} = \alpha \frac{N \sqrt{2Q}}{\sqrt 3} = \frac{\sqrt 2}{\sqrt 3} \alpha N \sqrt Q)となって額面では$ 1.22倍ほど高速になる。
もちろんこのバケットサイズは整数にはならないし、この計算は概算程度だと思っていただきたい(しかし実際かなり高速にはなった)。
例題
制約的にかなり厳しそうだがなんとかなる。