Mo's algorithm （区間クエリに関する平方分割テクニック）
(other_algorithms/mos_algorithm.hpp)

• View this file on GitHub
• Last update: 2024-12-28 06:16:13+09:00
• Include: #include "other_algorithms/mos_algorithm.hpp"
• Link: https://codeforces.com/contest/375/submission/114665433

使用方法

vector<Result> ret(Q); // 答えを格納する領域
MosAlgorithm mo;
for (int q = 0; q < Q; q++) {
    mo.add_range(L[q], R[q]);
}
auto add = [&](int i) -> void { /* 区間を延ばして i 番目の要素を追加したときの処理 */ };
auto remove = [&](int i) -> void { /* 区間を縮めて i 番目の要素を削除したときの処理 */ };
auto solve = [&](int q) -> void { ret[q] = f(q); /* q 個目のクエリを解く処理 */ };

mo.run(add, remove, solve);

for (auto x : ret) cout << x << '\n';

最適なバケット幅設定

列の長さを $N$, クエリを $Q$ 個とする．バケット幅を $W$ とするとバケット個数は $B = N / W$ 程度．

このとき，Add/Remove 演算は $BN + QW = \frac{N^2}{W} + QW$ 回程度生じる．これを最小にするのは $W = N / \sqrt{Q}$ と設定したときで，全体計算量は $O(N \sqrt{Q} \cdot C_\mathrm{Add/Erase} + Q \cdot C_\mathrm{query})$ となる．

問題例

• Codeforces Round #221 (Div. 1) D. Tree and Queries
  • 部分木クエリにも使用可能（ただし DSU on tree でもより良い最悪計算量で同様のことが可能）．

Links

• Codeforces blog のコメント : “Mo’s algorithm” の起源に関する議論．
• Mo’s algorithm - ei1333の日記
  • 木の部分木クエリやパスクエリに対する Mo’s algorithm の応用にも触れられている．

Code

#pragma once
#include <cassert>
#include <cmath>
#include <utility>
#include <vector>

// Mo's algorithm
// - add_range(l, r) : Add [l, r) as query.
// - run(Add, Remove, Query) : run Mo's algorithm.
//   - Add(i) : Add i-th element ([i + 1, r) -> [i, r)).
//   - Remove(i) : Remove i-th element (Inverse of Add(i)).
//   - Query(q) : Solve q-th problem.
// Verified: https://codeforces.com/contest/375/submission/114665433
class MosAlgorithm {
    static const int INF = 1 << 30;
    int nmin, nmax;

public:
    std::vector<std::pair<int, int>> ranges;
    MosAlgorithm() : nmin(INF), nmax(-INF) {}

    void add_range(int l, int r) {
        assert(l <= r);
        nmin = std::min(nmin, l);
        nmax = std::max(nmax, r);
        ranges.emplace_back(l, r);
    }
    template <typename F1, typename F2, typename F3, typename F4, typename F5>
    void run(F1 AddRight, F2 AddLeft, F3 RemoveRight, F4 RemoveLeft, F5 Query) {
        const int Q = ranges.size();
        if (!Q) return;
        const int nbbucket = std::max(1, std::min<int>(nmax - nmin, sqrt(Q)));
        const int szbucket = (nmax - nmin + nbbucket - 1) / nbbucket;
        std::vector<int> qs(Q);
        std::iota(qs.begin(), qs.end(), 0);
        std::sort(qs.begin(), qs.end(), [&](int q1, int q2) {
            int b1 = (ranges[q1].first - nmin) / szbucket, b2 = (ranges[q2].first - nmin) / szbucket;
            if (b1 != b2)
                return b1 < b2;
            else {
                return (b1 & 1) ? (ranges[q1].second > ranges[q2].second)
                                : (ranges[q1].second < ranges[q2].second);
            }
        });

        int l = ranges[qs[0]].first, r = l;
        for (auto q : qs) {
            while (r < ranges[q].second) AddRight(r++);
            while (l > ranges[q].first) AddLeft(--l);
            while (r > ranges[q].second) RemoveRight(--r);
            while (l < ranges[q].first) RemoveLeft(l++);
            assert(l == ranges[q].first and r == ranges[q].second);
            Query(q);
        }
    }
    template <typename F1, typename F3, typename F5> void run(F1 Add, F3 Remove, F5 Query) {
        run(Add, Add, Remove, Remove, Query);
    }
};

#line 2 "other_algorithms/mos_algorithm.hpp"
#include <cassert>
#include <cmath>
#include <utility>
#include <vector>

// Mo's algorithm
// - add_range(l, r) : Add [l, r) as query.
// - run(Add, Remove, Query) : run Mo's algorithm.
//   - Add(i) : Add i-th element ([i + 1, r) -> [i, r)).
//   - Remove(i) : Remove i-th element (Inverse of Add(i)).
//   - Query(q) : Solve q-th problem.
// Verified: https://codeforces.com/contest/375/submission/114665433
class MosAlgorithm {
    static const int INF = 1 << 30;
    int nmin, nmax;

public:
    std::vector<std::pair<int, int>> ranges;
    MosAlgorithm() : nmin(INF), nmax(-INF) {}

    void add_range(int l, int r) {
        assert(l <= r);
        nmin = std::min(nmin, l);
        nmax = std::max(nmax, r);
        ranges.emplace_back(l, r);
    }
    template <typename F1, typename F2, typename F3, typename F4, typename F5>
    void run(F1 AddRight, F2 AddLeft, F3 RemoveRight, F4 RemoveLeft, F5 Query) {
        const int Q = ranges.size();
        if (!Q) return;
        const int nbbucket = std::max(1, std::min<int>(nmax - nmin, sqrt(Q)));
        const int szbucket = (nmax - nmin + nbbucket - 1) / nbbucket;
        std::vector<int> qs(Q);
        std::iota(qs.begin(), qs.end(), 0);
        std::sort(qs.begin(), qs.end(), [&](int q1, int q2) {
            int b1 = (ranges[q1].first - nmin) / szbucket, b2 = (ranges[q2].first - nmin) / szbucket;
            if (b1 != b2)
                return b1 < b2;
            else {
                return (b1 & 1) ? (ranges[q1].second > ranges[q2].second)
                                : (ranges[q1].second < ranges[q2].second);
            }
        });

        int l = ranges[qs[0]].first, r = l;
        for (auto q : qs) {
            while (r < ranges[q].second) AddRight(r++);
            while (l > ranges[q].first) AddLeft(--l);
            while (r > ranges[q].second) RemoveRight(--r);
            while (l < ranges[q].first) RemoveLeft(l++);
            assert(l == ranges[q].first and r == ranges[q].second);
            Query(q);
        }
    }
    template <typename F1, typename F3, typename F5> void run(F1 Add, F3 Remove, F5 Query) {
        run(Add, Add, Remove, Remove, Query);
    }
};

Back to top page