Rollback Mo
(Src/DataStructure/Mo/RollbackMo.hpp)

• View this file on GitHub
• Last update: 2025-09-26 14:43:59+09:00
• Include: #include "Src/DataStructure/Mo/RollbackMo.hpp"

概要

Rollback Mo

Moからdel関数をrollbackに置き換えられるように工夫したMo’s Algorithm。

ライブラリの使い方

template <class T, class RBT, class Add, class Rollback, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize, const RBT&>> RollbackMo(const std::vector<T>& qs, Add addL, Add addR, Rollback rollback, Eval eval) {

面倒でコンセプトを書いていない(カス)

T

クエリの区間を表すclass。以下をコピれば基本的に問題無い。

struct Query {
    usize l, r;
};

RBT

ロールバックで管理させるデータを全部classにまとめてこれに指定する。

RBTのデフォルトコンストラクタが単位元である必要がある。

Add

usize, RBTをこの順に引数に取り、RBTを返す関数。引数の前者は追加する要素(添字に値するもの)、RBTは現在のデータが与えられる。

要素を追加した後のデータを返せば良い。

Rollback

RBTを引数に取る関数。引数に与えられたデータを用いてRBTで管理できないデータ(配列などの沢山メモリを食べるもの)をロールバックさせる。

• そのため、RBTには配列に対する「最後の操作」なども管理させると良い

Eval

usize, RBTをこの順に引数に取る関数。引数の前者はクエリの番号、後者は現在のデータである。

クエリをデータで評価して、評価結果を返せば良い。

使用例

例えば区間最頻値クエリをMoに投げるとき、以下のようにする。

struct Query {
    usize l, r;
};
struct Data {
    int top = -1, last = -1;
};
vector<int> cnt(ssize(comp));
auto add = [&](int i, Data d) {
    cnt[A[i]]++;
    if (d.top == -1 or cnt[A[i]] > cnt[d.top])
        d.top = A[i];
    d.last = A[i];
    return d;
};
auto rollback = [&](const Data& d) {
    cnt[d.last]--;
};
auto eval = [&](int, const Data& d) -> pair<int, int> {
    return {comp.inverse(d.top), cnt[d.top]};
};
for (auto [a, b] : RollbackMo<Query, Data, decltype(add), decltype(rollback), decltype(eval)>(q, add, add, rollback, eval))
    cout << a << ' ' << b << '\n';

計算量

以下の合計となる。

• addLを $O(Q\sqrt{N})$ 回呼び出す
• addRを $O((N + Q)\sqrt{N})$ 回呼び出す
• addL, addRを呼び出した回数の合計と同じ回数だけrollbackを呼び出す
• evalを $Q$ 回呼び出す
• $O((N + Q)\sqrt{N} + Q\log Q)$ (カウンタの管理やソートなど)

ロールバックの管理に関して、vector<RBT>を一個用いており、この要素数の最大は実行全体で高々 $N$ 個になる。

Depends on

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

Verified with

• Test/CF/CF1054-G.test.cpp
• Test/LC/static_range_mode_query.test.cpp

Code

#pragma once

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

#include <algorithm>
#include <cassert>
#include <concepts>
#include <limits>
#include <utility>
#include <vector>

namespace zawa {

template <class T, class RBT, class Add, class Rollback, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize, const RBT&>> RollbackMo(const std::vector<T>& qs, Add addL, Add addR, Rollback rollback, Eval eval) {
    const usize n = [&]() {
        usize mx = 0;
        for (usize i = 0 ; i < qs.size() ; i++) {
            assert(qs[i].l <= qs[i].r);
            mx = std::max<usize>(mx, qs[i].r);
        }
        return mx;
    }();
    const usize SQ = [&]() {
        usize i = 1;
        while (i * i < n)
            i++;
        return i;
    }();
    std::vector<std::vector<std::pair<usize, usize>>> rs((n + SQ - 1) / SQ);
    std::vector<typename std::invoke_result_t<Eval, usize, const RBT&>> res(qs.size());
    std::vector<RBT> history;
    history.emplace_back();
    for (usize i = 0 ; i < qs.size() ; i++) {
        if (qs[i].r - qs[i].l <= SQ) {
            for (usize j = qs[i].l ; j < qs[i].r ; j++)
                history.push_back(addR(j, history.back()));
            res[i] = eval(i, history.back());
            for (usize j = qs[i].l ; j < qs[i].r ; j++) {
                rollback(history.back());
                history.pop_back();
            }
        }
        else
            rs[qs[i].l / SQ].emplace_back(qs[i].r, i);
    }
    for (usize i = 0 ; i < rs.size() ; i++)
        if (rs[i].size()) {
            std::sort(rs[i].begin(), rs[i].end());
            const usize L = (i + 1) * SQ;
            usize R = L;
            for (auto [r, idx] : rs[i]) {
                while (R < r)
                    history.push_back(addR(R++, history.back()));
                for (usize j = L ; j > qs[idx].l ; )
                    history.push_back(addL(--j, history.back()));
                res[idx] = eval(idx, history.back());
                for (usize j = L ; j > qs[idx].l ; j--) {
                    rollback(history.back());
                    history.pop_back();
                }
            }
            for (usize j = L ; j < R ; j++) {
                rollback(history.back());
                history.pop_back();
            }
        }
    return res;
}

} // namespace zawa

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

#include <algorithm>
#include <cassert>
#include <concepts>
#include <limits>
#include <utility>
#include <vector>

namespace zawa {

template <class T, class RBT, class Add, class Rollback, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize, const RBT&>> RollbackMo(const std::vector<T>& qs, Add addL, Add addR, Rollback rollback, Eval eval) {
    const usize n = [&]() {
        usize mx = 0;
        for (usize i = 0 ; i < qs.size() ; i++) {
            assert(qs[i].l <= qs[i].r);
            mx = std::max<usize>(mx, qs[i].r);
        }
        return mx;
    }();
    const usize SQ = [&]() {
        usize i = 1;
        while (i * i < n)
            i++;
        return i;
    }();
    std::vector<std::vector<std::pair<usize, usize>>> rs((n + SQ - 1) / SQ);
    std::vector<typename std::invoke_result_t<Eval, usize, const RBT&>> res(qs.size());
    std::vector<RBT> history;
    history.emplace_back();
    for (usize i = 0 ; i < qs.size() ; i++) {
        if (qs[i].r - qs[i].l <= SQ) {
            for (usize j = qs[i].l ; j < qs[i].r ; j++)
                history.push_back(addR(j, history.back()));
            res[i] = eval(i, history.back());
            for (usize j = qs[i].l ; j < qs[i].r ; j++) {
                rollback(history.back());
                history.pop_back();
            }
        }
        else
            rs[qs[i].l / SQ].emplace_back(qs[i].r, i);
    }
    for (usize i = 0 ; i < rs.size() ; i++)
        if (rs[i].size()) {
            std::sort(rs[i].begin(), rs[i].end());
            const usize L = (i + 1) * SQ;
            usize R = L;
            for (auto [r, idx] : rs[i]) {
                while (R < r)
                    history.push_back(addR(R++, history.back()));
                for (usize j = L ; j > qs[idx].l ; )
                    history.push_back(addL(--j, history.back()));
                res[idx] = eval(idx, history.back());
                for (usize j = L ; j > qs[idx].l ; j--) {
                    rollback(history.back());
                    history.pop_back();
                }
            }
            for (usize j = L ; j < R ; j++) {
                rollback(history.back());
                history.pop_back();
            }
        }
    return res;
}

} // namespace zawa

Back to top page