Mo's algorithm
(src/others/mo.hpp)

View this file on GitHub
Last update: 2026-10-12 20:24:58+09:00
Include: #include "src/others/mo.hpp"

区間 $[l, r)$ に対するクエリをまとめて先読みし、区間の端を 1 つずつ伸び縮みさせながら答えます。区間に要素を 1 つ追加・削除する操作が速くできるときに使えます。

// 各クエリ [l, r) の、区間内の異なる値の個数
std::vector<int> cnt(MAXA);
auto add = [&](int& kinds, int i) { if (cnt[a[i]]++ == 0) kinds++; };
auto del = [&](int& kinds, int i) { if (--cnt[a[i]] == 0) kinds--; };
Mo mo(n, 0, add, del);                  // 左右で同じ操作なら 2 つ渡せばよい
for (auto [l, r] : queries) mo.query(l, r);
std::vector<int> ans = mo.solve<int>([](int& kinds) { return kinds; });  // クエリ順の答え

使い方

関数	説明
`Mo(n, e, add_left, delete_left, add_right, delete_right)`	要素数 `n`、状態の初期値 `e` (型 `U`) と 4 つの操作で作る
`Mo(n, e, add, del)`	左端と右端で操作が同じ場合
`query(l, r)`	クエリ $[l, r)$ を追加する
`solve<T>(f)`	すべてのクエリを処理し、各クエリで `f(state)` が返した値 (型 `T`) を、`query` を呼んだ順に並べて返す

操作はいずれも (U& state, int i) を受け取り、state を書き換えます。

操作	呼ばれるとき
`add_left(state, i)`	区間の左に要素 `i` を追加する
`delete_left(state, i)`	区間の左端の要素 `i` を削除する
`add_right(state, i)`	区間の右に要素 `i` を追加する
`delete_right(state, i)`	区間の右端の要素 `i` を削除する

操作が $O(1)$ のとき、全体の計算量は $O(n \sqrt{q} + q \log q)$ です ($q$ はクエリ数)。

Verified with

Code

#pragma once

/**
 * @file mo.hpp
 * @brief Mo's algorithm
 */

#include <vector>
#include <array>
#include <type_traits>
#include <algorithm>
#include <cmath>

template <typename U, class ADD_LEFT, class DELETE_LEFT, class ADD_RIGHT = ADD_LEFT, class DELETE_RIGHT = DELETE_LEFT>
struct Mo {
   private:
    int _n;
    std::vector<std::array<int, 3>> lri;
    U _e;
    ADD_LEFT _add_left;
    DELETE_LEFT _delete_left;
    ADD_RIGHT _add_right;
    DELETE_RIGHT _delete_right;

    static_assert(std::is_invocable_r_v<void, ADD_LEFT, U&, int>, "ADD_LEFT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, DELETE_LEFT, U&, int>, "DELETE_LEFT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, ADD_RIGHT, U&, int>, "ADD_RIGHT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, DELETE_RIGHT, U&, int>, "DELETE_RIGHT must be callable with (U&, int)");

   public:
    Mo(int n,
       const U& e,
       const ADD_LEFT& add_left,
       const DELETE_LEFT& delete_left,
       const ADD_RIGHT& add_right,
       const DELETE_RIGHT& delete_right) : _n(n), lri(), _e(e), _add_left(add_left), _delete_left(delete_left), _add_right(add_right), _delete_right(delete_right) {}
    Mo(int n,
       const U& e,
       const ADD_LEFT& add_left,
       const DELETE_LEFT& delete_left) : _n(n), lri(), _e(e), _add_left(add_left), _delete_left(delete_left), _add_right(add_left), _delete_right(delete_left) {}
    void query(int l, int r) {
        lri.push_back({l, r, (int)lri.size()});
    }
    template <typename T, class F>
    std::vector<T> solve(const F& f) {
        static_assert(std::is_invocable_r_v<T, F, U&>, "The function passed to solve must be callable with (U&) and return T");
        
        const int w = std::max<int>(1, 1.0 * _n / std::max<double>(1.0, std::sqrt(lri.size() * 2.0 / 3.0)));
        std::sort(lri.begin(), lri.end(), [=](const std::array<int, 3>& a, const std::array<int, 3>& b) {
            int aw = a[0] / w;
            int bw = b[0] / w;
            if (aw != bw) return aw < bw;
            if (aw & 1) return a[1] > b[1];
            return a[1] < b[1];
        });
        std::vector<T> res(lri.size());
        long long tmpl = 0, tmpr = 0;
        U tmp = _e;
        for (auto [l, r, i] : lri) {
            while (tmpl > l) {
                tmpl--;
                _add_left(tmp, tmpl);
            }
            while (tmpr < r) {
                _add_right(tmp, tmpr);
                tmpr++;
            }
            while (tmpl < l) {
                _delete_left(tmp, tmpl);
                tmpl++;
            }
            while (tmpr > r) {
                tmpr--;
                _delete_right(tmp, tmpr);
            }
            res[i] = f(tmp);
        }
        return res;
    }
};

#line 2 "src/others/mo.hpp"

/**
 * @file mo.hpp
 * @brief Mo's algorithm
 */

#include <vector>
#include <array>
#include <type_traits>
#include <algorithm>
#include <cmath>

template <typename U, class ADD_LEFT, class DELETE_LEFT, class ADD_RIGHT = ADD_LEFT, class DELETE_RIGHT = DELETE_LEFT>
struct Mo {
   private:
    int _n;
    std::vector<std::array<int, 3>> lri;
    U _e;
    ADD_LEFT _add_left;
    DELETE_LEFT _delete_left;
    ADD_RIGHT _add_right;
    DELETE_RIGHT _delete_right;

    static_assert(std::is_invocable_r_v<void, ADD_LEFT, U&, int>, "ADD_LEFT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, DELETE_LEFT, U&, int>, "DELETE_LEFT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, ADD_RIGHT, U&, int>, "ADD_RIGHT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, DELETE_RIGHT, U&, int>, "DELETE_RIGHT must be callable with (U&, int)");

   public:
    Mo(int n,
       const U& e,
       const ADD_LEFT& add_left,
       const DELETE_LEFT& delete_left,
       const ADD_RIGHT& add_right,
       const DELETE_RIGHT& delete_right) : _n(n), lri(), _e(e), _add_left(add_left), _delete_left(delete_left), _add_right(add_right), _delete_right(delete_right) {}
    Mo(int n,
       const U& e,
       const ADD_LEFT& add_left,
       const DELETE_LEFT& delete_left) : _n(n), lri(), _e(e), _add_left(add_left), _delete_left(delete_left), _add_right(add_left), _delete_right(delete_left) {}
    void query(int l, int r) {
        lri.push_back({l, r, (int)lri.size()});
    }
    template <typename T, class F>
    std::vector<T> solve(const F& f) {
        static_assert(std::is_invocable_r_v<T, F, U&>, "The function passed to solve must be callable with (U&) and return T");
        
        const int w = std::max<int>(1, 1.0 * _n / std::max<double>(1.0, std::sqrt(lri.size() * 2.0 / 3.0)));
        std::sort(lri.begin(), lri.end(), [=](const std::array<int, 3>& a, const std::array<int, 3>& b) {
            int aw = a[0] / w;
            int bw = b[0] / w;
            if (aw != bw) return aw < bw;
            if (aw & 1) return a[1] > b[1];
            return a[1] < b[1];
        });
        std::vector<T> res(lri.size());
        long long tmpl = 0, tmpr = 0;
        U tmp = _e;
        for (auto [l, r, i] : lri) {
            while (tmpl > l) {
                tmpl--;
                _add_left(tmp, tmpl);
            }
            while (tmpr < r) {
                _add_right(tmp, tmpr);
                tmpr++;
            }
            while (tmpl < l) {
                _delete_left(tmp, tmpl);
                tmpl++;
            }
            while (tmpr > r) {
                tmpr--;
                _delete_right(tmp, tmpr);
            }
            res[i] = f(tmp);
        }
        return res;
    }
};

Mo's algorithm (src/others/mo.hpp)

使い方

Verified with

Code

Mo's algorithm
(src/others/mo.hpp)