モー隊（Mo's Algorithm）は、範囲クエリをオフラインで効率的に処理するためのアルゴリズムです。本質的には平方分割の考え方を応用したもので、クエリの順序を工夫することで計算量を削減します。

標準的なモー隊

標準的なモー隊は、静的な配列に対する範囲クエリに使用されます。

基本的な考え方

1. 配列をサイズ $B = \frac{n}{\sqrt{m}}$ のブロックに分割します。
2. 各クエリ $[L, R]$ を以下の優先度でソートします：
   • 左端 $L$ が属するブロックの番号
   • 右端 $R$ の昇順（左端が同じブロック内にある場合）
3. 左ポインタと右ポインタを移動させながら、各クエリの解を求めます。

このアルゴリズムの計算量は $O(n\sqrt{n})$ です。

最適化：ジグザグソート

右端の移動距離を短縮するために、左端が属するブロックが奇数番目か偶数番目かで、右端のソート順（昇順・降順）を切り替える手法が一般的です。

struct Query {
    int left, right, id, block_idx;
    bool operator<(const Query& other) const {
        if (block_idx != other.block_idx) {
            return block_idx < other.block_idx;
        }
        if (block_idx & 1) {
            return right < other.right;
        }
        return right > other.right;
    }
};

void solve() {
    int current_l = 1, current_r = 0;
    for (int i = 0; i < query_count; i++) {
        int target_l = queries[i].left;
        int target_r = queries[i].right;

        while (current_l > target_l) add(--current_l);
        while (current_r < target_r) add(++current_r);
        while (current_l < target_l) remove(current_l++);
        while (current_r > target_r) remove(current_r--);

        results[queries[i].id] = current_answer;
    }
}

修正可能モー隊

一点更新が含まれる場合、時間軸を追加して「3次元のモー隊」として扱います。

ソート順序

1. 左端 $L$ のブロック番号
2. 右端 $R$ のブロック番号
3. 時間 $T$ (更新回数)

ブロックサイズを $O(n^{2/3})$ に設定することで、全体の計算量は $O(n^{5/3})$ となります。

struct ModQuery {
    int l, r, time, id, lb, rb;
    bool operator<(const ModQuery& o) const {
        if (lb != o.lb) return lb < o.lb;
        if (rb != o.rb) return rb < o.rb;
        return time < o.time;
    }
};

void apply_update(int t, int ql, int qr) {
    if (updates[t].pos >= ql && updates[t].pos <= qr) {
        remove(a[updates[t].pos]);
        add(updates[t].new_val);
    }
    swap(a[updates[t].pos], updates[t].new_val);
}

木上のモー隊

木のパスや部分木に対するクエリも、配列上の問題に変換することでモー隊を適用できます。

部分木クエリ

DFS順（行きがけ順）を利用して、部分木を一つの連続した区間に変換します。

パスクエリ

オイラーツアー（括弧序）を利用します。各頂点 $u$ が最初に出現する時間を $st[u]$、最後に出現する時間を $en[u]$ とします。パス $u \to v$ ($st[u] < st[v]$) は以下のように変換されます。

• $LCA(u, v) = u$ の場合：区間は $[st[u], st[v]]$
• それ以外の場合：区間は $[en[u], st[v]]$ に $LCA(u, v)$ を加えたもの

出現回数が2回になった頂点は、パスに含まれないものとして除外します。

ロールバックモー隊（不退却モー隊）

要素の追加は容易だが、削除が困難または不可能な場合に使用します。

アルゴリズムの流れ

1. クエリを左端のブロックごとにグループ化します。
2. 右端ポインタはブロック内で単調増加させ、削除を行わないようにします。
3. 左端ポインタは各クエリごとにブロックの右端から左へ移動させ、クエリ終了後に「ロールバック（状態を戻す）」します。

二次離線モー隊

モー隊のポインタ移動時の更新 $O(k)$ が重い場合、その更新自体をさらにオフラインで処理する手法です。 寄与分を差分計算の形 $f(x, [1, x-1]) - f(x, [1, l-1])$ に分解します。

• 第1項 $f(x, [1, x-1])$ は前処理で計算可能です。
• 第2項 $f(x, [1, l-1])$ は、再度スキャンを行い、フェニック木などのデータ構造を用いて一括処理します。

これにより、計算量を $O(nk + n\sqrt{n})$ 程度に抑えることが可能になります。