Mo's algorithm
(Src/DataStructure/Mo/Mo.hpp)

View this file on GitHub
Last update: 2025-04-14 13:20:45+09:00
Include: #include "Src/DataStructure/Mo/Mo.hpp"
Link: https://codeforces.com/blog/entry/61203?#comment-1064868

概要

Mo’s Algorithm

ライブラリの使い方

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

T

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

符号なし整数型のメンバ変数l、rをpublic下に持つクラスである必要がある
lが半開区間の左端、rが半開区間の右端を意味する

Tは基本的には以下をコピれば問題無いはず。

struct query {
    usize l, r;
};

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)

参考

Depends on

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

Verified with

Code

#pragma once

#include "../../Template/TypeAlias.hpp"

#include <algorithm>
#include <bit>
#include <cassert>
#include <vector>
#include <type_traits>

namespace zawa {

namespace internal {

// reference: https://codeforces.com/blog/entry/61203?#comment-1064868
u64 hilbertOrder(u64 x, u64 y, usize dim) {
    const u64 max{(1ull << dim) - 1};
    assert(x <= max);
    assert(y <= max);
    u64 res{};
    for (u64 s{1ull << (dim - 1)} ; s ; s >>= 1) {
        bool rx{static_cast<bool>(x & s)}, ry{static_cast<bool>(y & s)};
        res = (res << 2) | (rx ? ry ? 2 : 1 : ry ? 3 : 0);
        if (!rx) {
            if (ry) x ^= max, y ^= max;
            std::swap(x, y);
        }
    }
    return res;
}

} // namespace internal

template <class T, class AddL, class AddR, class DelL, class DelR, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize>> Mo(std::vector<T> qs, AddL addL, AddR addR, DelL delL, DelR delR, Eval eval, bool reset = false) {
    usize log{};
    for (const T& lr : qs) log = std::max<usize>(log, std::bit_width(lr.r));
    std::vector<std::pair<T, usize>> ord(qs.size());
    std::vector<u64> h(qs.size());
    for (usize i{} ; i < qs.size() ; i++) {
        ord[i] = {qs[i], i};
        h[i] = internal::hilbertOrder(qs[i].l, qs[i].r, log);
    }
    std::sort(ord.begin(), ord.end(), [&](const auto& L, const auto& R) -> bool {
            return h[L.second] < h[R.second];
            });
    std::vector<typename std::invoke_result_t<Eval, usize>> res(qs.size());
    usize L{}, R{};
    for (const auto& [lr, id] : ord) {
        while (R < lr.r) addR(R++);
        while (L > lr.l) addL(--L);
        while (R > lr.r) delR(--R);
        while (L < lr.l) delL(L++);
        res[id] = eval(id);
    }
    if (reset) while (R > L) delR(--R);
    return res;
}

} // namespace zawa

#line 2 "Src/DataStructure/Mo/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/DataStructure/Mo/Mo.hpp"

#include <algorithm>
#include <bit>
#include <cassert>
#include <vector>
#include <type_traits>

namespace zawa {

namespace internal {

// reference: https://codeforces.com/blog/entry/61203?#comment-1064868
u64 hilbertOrder(u64 x, u64 y, usize dim) {
    const u64 max{(1ull << dim) - 1};
    assert(x <= max);
    assert(y <= max);
    u64 res{};
    for (u64 s{1ull << (dim - 1)} ; s ; s >>= 1) {
        bool rx{static_cast<bool>(x & s)}, ry{static_cast<bool>(y & s)};
        res = (res << 2) | (rx ? ry ? 2 : 1 : ry ? 3 : 0);
        if (!rx) {
            if (ry) x ^= max, y ^= max;
            std::swap(x, y);
        }
    }
    return res;
}

} // namespace internal

template <class T, class AddL, class AddR, class DelL, class DelR, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize>> Mo(std::vector<T> qs, AddL addL, AddR addR, DelL delL, DelR delR, Eval eval, bool reset = false) {
    usize log{};
    for (const T& lr : qs) log = std::max<usize>(log, std::bit_width(lr.r));
    std::vector<std::pair<T, usize>> ord(qs.size());
    std::vector<u64> h(qs.size());
    for (usize i{} ; i < qs.size() ; i++) {
        ord[i] = {qs[i], i};
        h[i] = internal::hilbertOrder(qs[i].l, qs[i].r, log);
    }
    std::sort(ord.begin(), ord.end(), [&](const auto& L, const auto& R) -> bool {
            return h[L.second] < h[R.second];
            });
    std::vector<typename std::invoke_result_t<Eval, usize>> res(qs.size());
    usize L{}, R{};
    for (const auto& [lr, id] : ord) {
        while (R < lr.r) addR(R++);
        while (L > lr.l) addL(--L);
        while (R > lr.r) delR(--R);
        while (L < lr.l) delL(L++);
        res[id] = eval(id);
    }
    if (reset) while (R > L) delR(--R);
    return res;
}

} // namespace zawa

Mo's algorithm (Src/DataStructure/Mo/Mo.hpp)

概要