Mo’s algorithm は、\(f(l, r)\) から \(f(l+dx, r+dy)\) が \(d=|dx|+|dy|\) として、\(O(d+N/\sqrt{Q})\) に求まるとき \(f(l, r)\) (\(0 \leq l, r \leq N\)) を求めよというクエリがオフラインで \(O(N\sqrt{Q}+Q\log(Q))\) で処理できる。
2次元平面の与えられた点を全て通る walk について、マンハッタン距離での最短化の近似アルゴリズムと考えることができる。\((iN/\sqrt{Q}, jN/\sqrt{Q})\) (\(i,j \in [\sqrt Q]\)) を訪れろというインスタンスは \(O(N\sqrt{Q})\) かかるため最悪計算量の観点では最適である。画像のような与えられた点を葉に持つ木を取り、その上をオイラーツアーすればよい。
\((-1, 0), (0, -1)\) 方向への移動は、履歴を roll back することで \((1, 0), (0, 1)\) 方向への移動と同じ計算量で（原理的には）必ずできる。従って、Moが適用できるか考察する際には、\((1, 0), (0, 1)\) 方向への移動だけ考えればよい。木の構造を左右反転すれば、\((-1, 0), (0, 1)\) 方向への移動だけにする子もできる。点の移動順をヒルベルト曲線上で訪れる順にしても同じ計算量が達成できる。これは cache oblivious と発想が近い。
処理できるクエリの例
- \(a_{l},\ldots,a_{r}\)の最頻値
- \(a_{l},\ldots,a_{r}\)の k 番目に小さい値
- \(a_{l},\ldots,a_{r}\)で同じ数をペアにしたとき、何個のペアができるか。(ABC242G)
- \(a_{l},\ldots,a_{r}\)には何種類の数があるか。(ABC174F)
- \(a_{l},\ldots,a_{r}\)の総積の約数の個数(dwacon2017e)
- \(a_{l},\ldots,a_{r}\)の和がKになる部分列の個数（CF442F）
- \(a_{l},\ldots,a_{r}\)に含まれる、同じ要素が複数回現れない連続部分列の個数（Hackensack 101 Hack 52 C）
- fをO(1)次方程式とする。\(a_{l},\ldots,a_{r}\) に出現する各値の登場回数 x について、f(x) の和を求めよ。
- \(a_{l},\ldots,a_{r}\) に現れる値 \(v\) とその出現回数 \(c\) の積 \(vc\) の最大値を \(O(Q N^{1/2})\) で求めよ（JOI歴史の研究）。
- \(a_{l},\ldots,a_{r}\) について、各値 \(v\) に出現回数 \(c\) との積 \(vc\) を割り当てる。この値の最大値と最小値の差 \(x\) が最小になるように \(k\) 項選ぶ。\(x\) の値を求めよ。(CF1476)
- \(\sum_{k=l_i}^{r_i}{n_i \choose k}\) を求めよ。
- n 頂点の木が与えられる。各頂点 i には色 \(v_i\in [n]\) が割り当てられている。\(w_i\)を根とする部分木に含まれる色の種類数を求めよ。
- n 頂点の木が与えられる。各頂点 i には色 \(v_i\in [n]\) が割り当てられている。\(u_i\)-\(w_i\)パスに含まれる色の種類数を求めよ。
- \(a_{l},\ldots,a_{r}\) の転倒数を\(O(QN^{1/2})\)で求めよ。
Comments