Mo's Algorithm

前これを使う問題をCodeforcesでみた(解けなかった)のでメモ。

a[1] ... a[N] (N=O(10^6)) に対し区間クエリQ(l, r)がO(10^6)個発行される。このクエリは先読み可能である。Q(l, r)の結果がわかっているときに隣接クエリQ(l±1, r), Q(l, r±1) の結果はO(1)とか(O(logN)も定数倍軽ければいけるけど)で計算可能、という状況で汎用的に使えるアルゴリズム。

一般にO(10^6)のクエリを発行する場合、O(QN)では間に合わないので、O(Q logQ + N logN)とかO(Q√N + N √N)といった計算量を目指す。前者はセグメント木や後者は平方分割であるが、これらの方法で単純にやると単位元付き半群の構造を入れる必要がある。そして結構思いつかないことも多い。(max-plus ringとか知らなかったら詰む)

一方でMo's Algorithmは純粋に計算量だけで判断可能なのでごくたまに役立つときがある。

さて、具体的なアルゴリズムの手順であるが、まずNを平方分割し、√Nのバケットを作る。次にクエリを先読みして、次の基準でソートする。

sort(query, (a, b) -> bucket[a.l] != bucket[b.l] ?  bucket[a.l] - bucket[b.l]  : a.r- b.r)

これはつまり、まずクエリのleft側をバケットに入れ、バケット別にソートし、更にバケットの中でright側の基準でソートするという2段階ソートである。

int i = 0, j = 0
for (q : queries) {
    while (i < l) Q[i, j] から Q[i + 1, j]を計算
    while (i > l) Q[i, j] から Q[i - 1, j]を計算
    while (j < r) Q[i, j] から Q[i, j + 1]を計算
    while (j > r) Q[i, j]からQ[i, j - 1]を計算

    ret[q.index] = 上のループの最後の結果
}

forの中に更にwhile文が4個あるが、これらよるループの総回数は最初のソートのお陰でO(N√N + Q√N)回になるのである。whileで計算したクエリは後で再利用するわけではないので、全て保存するわけではなく、実際には次のように書くことが多い。

int i = 0, j = 0
now = Q[0, 0] の結果
for (q : queries) {
    while (i < l) remove(now, a[i ++])
    while (i > l) add(now, a[-- i])
    while (j < r) add(now, a[++j])
    while (j > r) remove(now, a[j--])
    ret[q.index] = now
}

addやremoveは最新のクエリの計算結果から隣接クエリの結果を計算する関数である。