Mo's algorithm
(include/emthrm/misc/mo.hpp)

• View this file on GitHub
• Last update: 2026-09-21 19:26:16+09:00
• Include: #include "emthrm/misc/mo.hpp"

• オフラインである。
• 要素の更新がない。
• $\lbrack L, R \rbrack$ の結果から $\lbrack L - 1, R \rbrack,\ \lbrack L + 1, R \rbrack,\ \lbrack L, R - 1 \rbrack,\ \lbrack L, R + 1 \rbrack$ の結果が容易に得られる。

上記の条件を満たすことによって区間に関するクエリを高速に処理できるアルゴリズムである。

時間計算量

一回の伸縮あたり $O(\alpha)$ 時間かかるとおくと $O(Q\log{Q} + \alpha N\sqrt{Q})$

仕様

template <typename AddLeft, typename AddRight,
          typename DelLeft, typename DelRight>
struct Mo;

メンバ関数

名前	効果・戻り値	備考
explicit Mo(const std::vector<int>& ls, const std::vector<int>& rs, const AddLeft& add_left, const AddRight& add_right, const DelLeft& del_left, const DelRight& del_right);	クエリ集合 $\lbrace \lbrack \mathrm{ls}_i, \mathrm{rs}_i) \rbrace$ と、区間の左端・右端に対する追加・削除をそれぞれ指定してオブジェクトを構築する。
int process();	次のクエリを処理し、そのインデックスを返す。ただし存在しないときは $-1$ を返す。

参考文献

• https://codeforces.com/blog/entry/81716
• https://ei1333.hateblo.jp/entry/2017/09/11/211011
• https://snuke.hatenablog.com/entry/2016/07/01/000000

TODO

• https://www.hamayanhamayan.com/entry/2017/04/18/012937
• Rollback 平方分割
  • https://snuke.hatenablog.com/entry/2016/07/01/000000
  • https://lumakernel.github.io/ecasdqina/algorithm/MoEx
  • https://github.com/ei1333/library/blob/master/other/mo-rollback.hpp
• 木上の Mo’s algorithm、時空間 Mo’s algorithm
  • https://ei1333.hateblo.jp/entry/2017/09/11/211011
  • https://ei1333.github.io/algorithm/mo.html
  • https://lumakernel.github.io/ecasdqina/algorithm/Mo
  • https://lumakernel.github.io/ecasdqina/algorithm/Mo3D
  • https://twitter.com/heno_code/status/1518799816876118016
  • https://twitter.com/noya2ruler/status/1733116450586648702
  • https://codeforces.com/blog/entry/43230
  • https://codeforces.com/blog/entry/55574
  • 問題例 “Minimum Difference”
    • https://twitter.com/SSRS_cp/status/1355193120204312576

Submissons

https://judge.yosupo.jp/submission/404491

Required by

• 二項係数の prefix sum の多点評価 (include/emthrm/math/twelvefold_way/multipoint_binomial_prefix_sum.hpp)

Verified with

• 数学/写像12相/二項係数の prefix sum の多点評価 (test/math/twelvefold_way/multipoint_binomial_prefix_sum.test.cpp)
• その他/Mo's algorithm (test/misc/mo.test.cpp)

Code

#ifndef EMTHRM_MISC_MO_HPP_
#define EMTHRM_MISC_MO_HPP_

#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>

namespace emthrm {

template <typename AddLeft, typename AddRight,
          typename DelLeft, typename DelRight>
struct Mo {
  explicit Mo(const std::vector<int>& ls, const std::vector<int>& rs,
              const AddLeft& add_left, const AddRight& add_right,
              const DelLeft& del_left, const DelRight& del_right)
      : n(ls.size()), ptr(0), nl(0), nr(0), ls(ls), rs(rs),
        add_left(add_left), add_right(add_right),
        del_left(del_left), del_right(del_right) {
    const int width = (
        n == 0 ? 1
               : std::max(std::llround(std::ranges::max(rs) / std::sqrt(n)),
                          1LL));
    order.resize(n);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(),
              [&ls, &rs, width](const int a, const int b) -> bool {
                  if (ls[a] / width != ls[b] / width) return ls[a] < ls[b];
                  return (ls[a] / width) & 1 ? rs[a] < rs[b] : rs[a] > rs[b];
              });
  }

  int process() {
    if (ptr == n) [[unlikely]] return -1;
    const int id = order[ptr++];
    while (ls[id] < nl) {
      const int idx = --nl;
      add_left(idx, nl, nr);
    }
    while (nr < rs[id]) {
      const int idx = nr++;
      add_right(idx, nl, nr);
    }
    while (nl < ls[id]) {
      const int idx = nl++;
      del_left(idx, nl, nr);
    }
    while (rs[id] < nr) {
      const int idx = --nr;
      del_right(idx, nl, nr);
    }
    return id;
  }

 private:
  const int n;
  int ptr, nl, nr;
  std::vector<int> ls, rs, order;
  AddLeft add_left;
  AddRight add_right;
  DelLeft del_left;
  DelRight del_right;
};

}  // namespace emthrm

#endif  // EMTHRM_MISC_MO_HPP_

#line 1 "include/emthrm/misc/mo.hpp"



#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>

namespace emthrm {

template <typename AddLeft, typename AddRight,
          typename DelLeft, typename DelRight>
struct Mo {
  explicit Mo(const std::vector<int>& ls, const std::vector<int>& rs,
              const AddLeft& add_left, const AddRight& add_right,
              const DelLeft& del_left, const DelRight& del_right)
      : n(ls.size()), ptr(0), nl(0), nr(0), ls(ls), rs(rs),
        add_left(add_left), add_right(add_right),
        del_left(del_left), del_right(del_right) {
    const int width = (
        n == 0 ? 1
               : std::max(std::llround(std::ranges::max(rs) / std::sqrt(n)),
                          1LL));
    order.resize(n);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(),
              [&ls, &rs, width](const int a, const int b) -> bool {
                  if (ls[a] / width != ls[b] / width) return ls[a] < ls[b];
                  return (ls[a] / width) & 1 ? rs[a] < rs[b] : rs[a] > rs[b];
              });
  }

  int process() {
    if (ptr == n) [[unlikely]] return -1;
    const int id = order[ptr++];
    while (ls[id] < nl) {
      const int idx = --nl;
      add_left(idx, nl, nr);
    }
    while (nr < rs[id]) {
      const int idx = nr++;
      add_right(idx, nl, nr);
    }
    while (nl < ls[id]) {
      const int idx = nl++;
      del_left(idx, nl, nr);
    }
    while (rs[id] < nr) {
      const int idx = --nr;
      del_right(idx, nl, nr);
    }
    return id;
  }

 private:
  const int n;
  int ptr, nl, nr;
  std::vector<int> ls, rs, order;
  AddLeft add_left;
  AddRight add_right;
  DelLeft del_left;
  DelRight del_right;
};

}  // namespace emthrm

Back to top page