Mo's algorithm
(library/various/mo.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/various/mo.hpp"

Mo’s algorithm

できること

• 区間クエリを平方分割で管理
• 参考: https://ei1333.github.io/library/other/mo.hpp

計算量

• 区間長n, クエリ数qで初期化 Mo(n, q): $O(q)$
• クエリ追加 $[l, r) {}_{0 \le l \lt r \le n}$ add_query: $O(1)$
• クエリを処理 calclate_queries: $O(\alpha N \sqrt Q)$ ※区間を1伸縮させる計算量を $O(\alpha)$

使い方

int N, Q;
cin >> N >> Q;
vector<int> A(N);
for (int i = 0; i < N; ++i) {
    cin >> A[i];
}

// Moの初期化
Mo mo(N, Q);

// クエリの登録
for (int i = 0; i < Q; ++i) {
    int l, r;
    cin >> l >> r; // 0-indexed, 半開区間 [l, r) と想定
    mo.add_query(l, r);
}

// 状態を保持する変数
vector<int> count(1000001, 0); // 数値の出現回数（数値の最大値に合わせる）
int current_distinct_types = 0;
vector<int> results(Q); // 各クエリの結果格納用

// 1. 要素を追加する時の処理
auto add = [&](int i) {
    if (count[A[i]] == 0ll) {
        current_distinct_types++;
    }
    count[A[i]]++;
};

// 2. 要素を削除する時の処理
auto erase = [&](int i) {
    count[A[i]]--;
    if (count[A[i]] == 0ll) {
        current_distinct_types--;
    }
};

// 3. クエリに答える時の処理
auto query = [&](int idx) {
    results[idx] = current_distinct_types;
};

// 計算実行 (2) の左右区別しないバージョンを使用
mo.calclate_queries(add, erase, query);

// 結果出力
for (int i = 0; i < Q; ++i) {
    cout << results[i] << endl;
}

Verified with

• Mo's algorithmのテスト (tests/various.mo.test.cpp)

Code

#pragma once
struct Mo {
  private:
    int n, w;
    vector<int> ord;
    vector<pair<int, int>> lr;

  public:
    Mo(int n, int q) : n(n), ord(q) {
        w = max<int>(1ll, n / max(1.0, sqrt(q * 2.0 / 3.0)));
        iota(ord.begin(), ord.end(), 0ll);
        lr.reserve(q);
    }
    void add_query(int l, int r) {
        assert(0ll <= l and l < r and r <= n);
        lr.emplace_back(l, r);
    }
    template <typename AL, typename AR, typename EL, typename ER, typename Q>
    void calclate_queries(const AL &add_left, const AR &add_right,
                          const EL &erase_left, const ER &erase_right,
                          const Q &query) {
        assert(lr.size() == ord.size());
        vector<int> bs(n);
        for (int i = 0, cnt = 0, b = 0; i < n; i++) {
            bs[i] = b;
            if (++cnt == w) {
                ++b;
                cnt = 0;
            }
        }
        sort(ord.begin(), ord.end(), [&](int a, int b) {
            int a_block = bs[lr[a].first];
            int b_block = bs[lr[b].first];
            if (a_block != b_block) return a_block < b_block;
            if (a_block & 1) {
                return lr[a].second < lr[b].second;
            } else {
                return lr[a].second > lr[b].second;
            }
        });
        int l = 0, r = 0;
        for (auto idx : ord) {
            while (l > lr[idx].first) add_left(--l);
            while (r < lr[idx].second) add_right(r++);
            while (l < lr[idx].first) erase_left(l++);
            while (r > lr[idx].second) erase_right(--r);
            query(idx);
        }
    }
    template <typename A, typename E, typename Q>
    void calclate_queries(const A &add, const E &erase, const Q &query) {
        calclate_queries(add, add, erase, erase, query);
    }
};

#line 2 "library/various/mo.hpp"
struct Mo {
  private:
    int n, w;
    vector<int> ord;
    vector<pair<int, int>> lr;

  public:
    Mo(int n, int q) : n(n), ord(q) {
        w = max<int>(1ll, n / max(1.0, sqrt(q * 2.0 / 3.0)));
        iota(ord.begin(), ord.end(), 0ll);
        lr.reserve(q);
    }
    void add_query(int l, int r) {
        assert(0ll <= l and l < r and r <= n);
        lr.emplace_back(l, r);
    }
    template <typename AL, typename AR, typename EL, typename ER, typename Q>
    void calclate_queries(const AL &add_left, const AR &add_right,
                          const EL &erase_left, const ER &erase_right,
                          const Q &query) {
        assert(lr.size() == ord.size());
        vector<int> bs(n);
        for (int i = 0, cnt = 0, b = 0; i < n; i++) {
            bs[i] = b;
            if (++cnt == w) {
                ++b;
                cnt = 0;
            }
        }
        sort(ord.begin(), ord.end(), [&](int a, int b) {
            int a_block = bs[lr[a].first];
            int b_block = bs[lr[b].first];
            if (a_block != b_block) return a_block < b_block;
            if (a_block & 1) {
                return lr[a].second < lr[b].second;
            } else {
                return lr[a].second > lr[b].second;
            }
        });
        int l = 0, r = 0;
        for (auto idx : ord) {
            while (l > lr[idx].first) add_left(--l);
            while (r < lr[idx].second) add_right(r++);
            while (l < lr[idx].first) erase_left(l++);
            while (r > lr[idx].second) erase_right(--r);
            query(idx);
        }
    }
    template <typename A, typename E, typename Q>
    void calclate_queries(const A &add, const E &erase, const Q &query) {
        calclate_queries(add, add, erase, erase, query);
    }
};

Back to top page