Mo's algorithm
(Src/Sequence/MoRangeQuery.hpp)

• View this file on GitHub
• Last update: 2026-03-16 19:40:14+09:00
• Include: #include "Src/Sequence/MoRangeQuery.hpp"

概要

Mo’s Algorithm

ライブラリの使い方

template <std::signed_integral T, class AddL, class AddR, class DelL, class DelR, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize>> Mo(const std::vector<std::pair<T,T>>& qs, AddL addL, AddR addR, DelL delL, DelR delR, Eval eval, bool reset = false) {

T

クエリで与えられる区間の型

• firstが半開区間の左端、secondrが半開区間の右端を意味する
• 内部のMoアルゴリズムの都合上符号付整数である必要がある。区間クエリの用途に限らなければ、符号さえがついていれば浮動小数でもよいのだが、そういうコンセプトを知らなかったので整数になっている。

addL addR

それぞれ要素 $i$ を左 or 右に追加するときの処理を実行する関数オブジェクト。

注意すべきは、ライブラリがaddL, addRに渡す引数は数列添字や木の頂点番号に値するものであることに注意。

例えば、Range Count Distinctなら

auto add = [&](int i) { cnt[A[i]]++; } // cnt[i]++は間違い

のようにする。

delL delR

それぞれ要素 $i$ が左/右端にあるとき、これを削除するときの処理を行う関数オブジェクト

eval

$i$ 番目のクエリを処理する際の関数オブジェクト

• 返り値を持つ必要がある

reset

データ処理の最後に、残った要素をすべてdelしたいときにtrueを指定する。

• 例えばmulti test caseの問題で利用する(CF974-H.test)

参考

• An alternative sorting order for Mo’s algorithm
• Mo’s algorithm で解ける問題
• Mo’s algorithm
• Mo’s algorithm
• 定数倍が最適なMo’s Algorithm
  • これを採用している。ABC448-Fでは距離の総和が最大ケースにおいて $\9\times 10^9$ 程度であるものが $7.5\times 10^9$ 程度に削減されていることを確認した。
  • しかし、区間クエリに投げると前の実装(Hilbert Curve)より実測がかかっており厳しい気持ちに。思ったよりMoの順序の計算にネックがある可能性がある？

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)
• Src/Utility/Mo.hpp

Verified with

• Test/AtCoder/abc384_g.test.cpp
• Test/AtCoder/abc405.test.cpp
• Test/CF/CF974-H.test.cpp
• Test/LC/static_range_frequency.test.cpp

Code

#pragma once

#include <algorithm>
#include <concepts>
#include <ranges>

#include "../Utility/Mo.hpp"

namespace zawa {

template <std::signed_integral T, class AddL, class AddR, class DelL, class DelR, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize>> Mo(const std::vector<std::pair<T,T>>& qs, AddL addL, AddR addR, DelL delL, DelR delR, Eval eval, bool reset = false) {
    auto ord = Mo(qs);
    std::vector<typename std::invoke_result_t<Eval, usize>> res(qs.size());
    T L = 0, R = 0;
    for (usize i : ord) {
        const auto [l, r] = qs[i];
        while (R < r) 
            addR(R++);
        while (L > l) 
            addL(--L);
        while (R > r) 
            delR(--R);
        while (L < l) 
            delL(L++);
        res[i] = eval(i);
    }
    if (reset) 
        while (R > L) 
            delR(--R);
    return res;
}

} // namespace zawa

#line 2 "Src/Sequence/MoRangeQuery.hpp"

#include <algorithm>
#include <concepts>
#include <ranges>

#line 2 "Src/Utility/Mo.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Utility/Mo.hpp"

#line 6 "Src/Utility/Mo.hpp"
#include <cmath>
#line 9 "Src/Utility/Mo.hpp"
#include <utility>
#include <numeric>
#include <limits>
#include <vector>

namespace zawa {

template <std::signed_integral T>
std::vector<usize> Mo(const std::vector<std::pair<T,T>>& P) {
    if (P.empty())
        return {};
    T minY = std::numeric_limits<T>::max();
    const u64 W = [&]() {
        T minX = std::numeric_limits<T>::max();
        T maxX = std::numeric_limits<T>::min(), maxY = std::numeric_limits<T>::min();
        for (auto [x,y] : P) {
            minX = std::min(minX,x);
            maxX = std::max(maxX,x);
            minY = std::min(minY,y);
            maxY = std::max(maxY,y);
        }
        return std::max<u64>({1,u64(maxX-minX),u64(maxY-minY)});
    }();
    const usize B = [&]() {
        u64 sq = std::max<u64>(1,sqrt(P.size()));
        return (W + sq - 1) / sq;
    }();
    T sub = minY;
    auto makeRank = [&]() -> std::vector<std::pair<T,T>> {
        std::vector<std::pair<T,T>> res(P.size());
        for (usize i = 0 ; i < P.size() ; i++) {
            res[i].first = (P[i].second - sub) / B;
            res[i].second = (res[i].first & 1 ? -1 : 1) * P[i].first;
        }
        return res;
    };
    std::vector<usize> ord1(P.size()), ord2(P.size());
    std::iota(ord1.begin(),ord1.end(),0);
    std::iota(ord2.begin(),ord2.end(),0);
    auto rank = makeRank();
    std::ranges::sort(ord1,[&](usize i, usize j) { return rank[i] < rank[j]; });
    sub -= B / 2;
    rank = makeRank();
    std::ranges::sort(ord2,[&](usize i, usize j) { return rank[i] < rank[j]; });
    auto cost = [&](const std::vector<usize>& ord) {
        u64 res = 0;
        for (usize i = 0 ; i + 1 < ord.size() ; i++) {
            res += abs(P[ord[i+1]].first-P[ord[i]].first);
            res += abs(P[ord[i+1]].second-P[ord[i]].second);
        }
        return res;
    };
    return cost(ord1) <= cost(ord2) ? ord1 : ord2;
}

} // namespace zawa
#line 8 "Src/Sequence/MoRangeQuery.hpp"

namespace zawa {

template <std::signed_integral T, class AddL, class AddR, class DelL, class DelR, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize>> Mo(const std::vector<std::pair<T,T>>& qs, AddL addL, AddR addR, DelL delL, DelR delR, Eval eval, bool reset = false) {
    auto ord = Mo(qs);
    std::vector<typename std::invoke_result_t<Eval, usize>> res(qs.size());
    T L = 0, R = 0;
    for (usize i : ord) {
        const auto [l, r] = qs[i];
        while (R < r) 
            addR(R++);
        while (L > l) 
            addL(--L);
        while (R > r) 
            delR(--R);
        while (L < l) 
            delL(L++);
        res[i] = eval(i);
    }
    if (reset) 
        while (R > L) 
            delR(--R);
    return res;
}

} // namespace zawa

Back to top page