Mo のアルゴリズム — pres1dent.net

何をするアルゴリズムか

数列に対する区間クエリをオフラインでまとめて処理する平方分割テクニック。次の条件がそろうときに使える。

クエリが先に全部わかっている(オフライン)
区間の端に要素を 1 個追加 / 1 個削除する操作が高速(だいたい $O(1)$ や $O(\log N)$ )にできる

2 つの区間の結果をマージできる量ならセグ木の方が速いので、Mo の出番になるのは種類数のようにマージが効かない量。

典型例は「区間内の値の種類数」。種類数は区間のマージができないが、要素を 1 個足す・消すときの種類数の増減は出現回数のカウントで $O(1)$ で追える。

仕組み

区間 $[l, r)$ を 2 次元平面の点 $(l, r)$ とみなし、クエリを次の順に並べ替える。

$l$ を幅 $B$ のブロックに分け、ブロック番号 $\lfloor l / B \rfloor$ の昇順
同じブロック内では $r$ の昇順

この順にクエリを処理しながら、現在の区間 $[cl, cr)$ の両端をクエリの区間まで 1 ステップずつ伸縮させる。伸縮のたびに追加 / 削除操作でデータ構造を更新すれば、各クエリ時点での答えが得られる。

なぜ計算量が抑えられるか

端の移動回数を数える。

右端 $r$ : 同じブロック内では $r$ は単調増加なので、1 ブロックあたり高々 $N$ 回しか動かない。ブロックは $N / B$ 個なので合計 $O(N^2 / B)$
左端 $l$ : 各クエリで $l$ は同じブロック内(幅 $B$ )しか動かない(ブロックをまたぐ移動は全体で $O(N)$ )。合計 $O(QB)$

合計 $O(N^2 / B + QB)$ で、 $B = N / \sqrt{Q}$ とすると $O(N \sqrt{Q})$ 。 $B = \sqrt{N}$ とした $O((N + Q)\sqrt{N})$ で説明されることも多いが、 $Q$ が $N$ より小さいときは $N / \sqrt{Q}$ の方が得。これに 1 回あたりの追加 / 削除のコストが掛かる。

実装例

「区間内の値の種類数」( $1 \le a_i \le N$ 、クエリは 1-indexed の閉区間で与えられるとする)。テンプレート前提で solve() の中身だけ。

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    cin >> a;

    vector<int> l(q), r(q);  // 半開区間 [l, r) で持つ
    rep(i, q) {
        cin >> l[i] >> r[i];
        l[i]--;
    }

    int width = max(1, (int)(n / max(1.0, sqrt((double)q))));
    vector<int> order(q);
    iota(all(order), 0);
    sort(all(order), [&](int i, int j) {
        if (l[i] / width != l[j] / width) return l[i] < l[j];
        return r[i] < r[j];
    });

    vector<int> cnt(n + 1);
    int distinct = 0;
    auto add = [&](int i) { if (cnt[a[i]]++ == 0) distinct++; };
    auto del = [&](int i) { if (--cnt[a[i]] == 0) distinct--; };

    int cl = 0, cr = 0;
    vector<int> ans(q);
    for (int idx : order) {
        while (cl > l[idx]) add(--cl);
        while (cr < r[idx]) add(cr++);
        while (cl < l[idx]) del(cl++);
        while (cr > r[idx]) del(--cr);
        ans[idx] = distinct;
    }
    rep(i, q) cout << ans[i] << "\n";
}

伸縮の順番に注意。先に区間を広げてから縮める(add を先、del を後)と、途中で cl > cr になって出現回数が負になる事故を防げる。

注意点

オンラインクエリ(前の答えに依存して次のクエリが決まる)には使えない
値の範囲が大きいときは座標圧縮してから cnt を持つ
定数倍最適化として、奇数番目のブロックだけ $r$ を降順に処理する「奇偶ソート」がある(端の往復が減る)
削除が難しい問題では追加だけで済ませる rollback 平方分割という発展形があるが、削除が書けるなら普通の Mo の方が定数倍が軽い

参考

Mo’s algorithm - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ