rollback_mo.hpp¶
以回滚结构处理离线区间询问，避免删除操作；适合只能添加元素、但状态可以整体撤销的答案维护。
Complexity: Time: O((N + Q) sqrt(N)) add/rollback work with standard blocking. Space: O(N + Q).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((N + Q) sqrt(N)) add/rollback work with standard blocking.
/// Space: O(N + Q).
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline half-open range scheduler for rollbackable add-only states.
/// Each query uses add(position), snapshot(), rollback(token), and answer(id).
struct rollback_mo {
int n = 0;
std::vector<std::pair<int, int>> qs;
rollback_mo() = default;
explicit rollback_mo(int n_) : n(n_) { assert(n >= 0); }
int add_query(int l, int r) {
assert(0 <= l && l <= r && r <= n);
int id = int(qs.size());
qs.emplace_back(l, r);
return id;
}
template <class Add, class Snapshot, class Rollback, class Answer>
void run(Add add, Snapshot ss, Rollback rb, Answer ans) const {
if (qs.empty()) {
return;
}
int bs = std::max(1, int(std::sqrt(std::max(1, n))));
int nb = (n + bs - 1) / bs + 1;
std::vector<std::vector<int>> gs(nb);
auto a0 = ss();
for (int id = 0; id < int(qs.size()); id++) {
auto [l, r] = qs[id];
int blk = l / bs;
int br = std::min(n, (blk + 1) * bs);
if (r <= br) {
auto tok = ss();
for (int pos = l; pos < r; pos++) {
add(pos);
}
ans(id);
rb(tok);
} else {
gs[blk].push_back(id);
}
}
for (int blk = 0; blk < nb; blk++) {
auto &ord = gs[blk];
if (ord.empty()) {
continue;
}
std::sort(ord.begin(), ord.end(), [&](int a, int b) {
return qs[a].second < qs[b].second;
});
int br = std::min(n, (blk + 1) * bs);
int r = br;
for (int id : ord) {
auto [ql, qr] = qs[id];
while (r < qr) {
add(r++);
}
auto tok = ss();
for (int pos = br - 1; pos >= ql; pos--) {
add(pos);
}
ans(id);
rb(tok);
}
rb(a0);
}
}
};
} // namespace noya
#ifndef NOYA_ROLLBACK_MO_HPP
#define NOYA_ROLLBACK_MO_HPP 1
/// @complexity Time: O((N + Q) sqrt(N)) add/rollback work with standard blocking.
/// Space: O(N + Q).
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline half-open range scheduler for rollbackable add-only states.
/// Each query uses add(position), snapshot(), rollback(token), and answer(id).
struct rollback_mo {
int n = 0;
std::vector<std::pair<int, int>> qs;
rollback_mo() = default;
explicit rollback_mo(int n_) : n(n_) { assert(n >= 0); }
int add_query(int l, int r) {
assert(0 <= l && l <= r && r <= n);
int id = int(qs.size());
qs.emplace_back(l, r);
return id;
}
template <class Add, class Snapshot, class Rollback, class Answer>
void run(Add add, Snapshot ss, Rollback rb, Answer ans) const {
if (qs.empty()) {
return;
}
int bs = std::max(1, int(std::sqrt(std::max(1, n))));
int nb = (n + bs - 1) / bs + 1;
std::vector<std::vector<int>> gs(nb);
auto a0 = ss();
for (int id = 0; id < int(qs.size()); id++) {
auto [l, r] = qs[id];
int blk = l / bs;
int br = std::min(n, (blk + 1) * bs);
if (r <= br) {
auto tok = ss();
for (int pos = l; pos < r; pos++) {
add(pos);
}
ans(id);
rb(tok);
} else {
gs[blk].push_back(id);
}
}
for (int blk = 0; blk < nb; blk++) {
auto &ord = gs[blk];
if (ord.empty()) {
continue;
}
std::sort(ord.begin(), ord.end(), [&](int a, int b) {
return qs[a].second < qs[b].second;
});
int br = std::min(n, (blk + 1) * bs);
int r = br;
for (int id : ord) {
auto [ql, qr] = qs[id];
while (r < qr) {
add(r++);
}
auto tok = ss();
for (int pos = br - 1; pos >= ql; pos--) {
add(pos);
}
ans(id);
rb(tok);
}
rb(a0);
}
}
};
} // namespace noya
#endif // NOYA_ROLLBACK_MO_HPP
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <utility>
#include <vector>
/// @complexity Time: O((N + Q) sqrt(N)) add/rollback work with standard blocking.
/// Space: O(N + Q).
namespace noya {
/// @brief Offline half-open range scheduler for rollbackable add-only states.
/// Each query uses add(position), snapshot(), rollback(token), and answer(id).
struct rollback_mo {
int n = 0;
std::vector<std::pair<int, int>> qs;
rollback_mo() = default;
explicit rollback_mo(int n_) : n(n_) { assert(n >= 0); }
int add_query(int l, int r) {
assert(0 <= l && l <= r && r <= n);
int id = int(qs.size());
qs.emplace_back(l, r);
return id;
}
template <class Add, class Snapshot, class Rollback, class Answer>
void run(Add add, Snapshot ss, Rollback rb, Answer ans) const {
if (qs.empty()) {
return;
}
int bs = std::max(1, int(std::sqrt(std::max(1, n))));
int nb = (n + bs - 1) / bs + 1;
std::vector<std::vector<int>> gs(nb);
auto a0 = ss();
for (int id = 0; id < int(qs.size()); id++) {
auto [l, r] = qs[id];
int blk = l / bs;
int br = std::min(n, (blk + 1) * bs);
if (r <= br) {
auto tok = ss();
for (int pos = l; pos < r; pos++) {
add(pos);
}
ans(id);
rb(tok);
} else {
gs[blk].push_back(id);
}
}
for (int blk = 0; blk < nb; blk++) {
auto &ord = gs[blk];
if (ord.empty()) {
continue;
}
std::sort(ord.begin(), ord.end(), [&](int a, int b) {
return qs[a].second < qs[b].second;
});
int br = std::min(n, (blk + 1) * bs);
int r = br;
for (int id : ord) {
auto [ql, qr] = qs[id];
while (r < qr) {
add(r++);
}
auto tok = ss();
for (int pos = br - 1; pos >= ql; pos--) {
add(pos);
}
ans(id);
rb(tok);
}
rb(a0);
}
}
};
} // namespace noya