rollback_mo.hpp¶
以回滚结构处理离线区间询问，避免删除操作；适合只能添加元素、但状态可以整体撤销的答案维护。
Complexity: Time: \(O(Q \log (Q + 1))\) sorting and \(O(N \sqrt{Q} + Q)\) add/undo steps. Callback costs apply to these steps. Space: \(O(Q)\) scheduler storage.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(Q log(Q+1)) sorting and O(N sqrt(Q) + Q) add/undo steps.
/// Callback costs apply to these steps. Space: O(Q) scheduler storage.
#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).
/// Answers must depend on the included positions, not their insertion order.
/// The caller's initial state is restored before run() returns.
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 left = n, right = 0, last_left = 0, count = 0;
for (auto [l, r] : qs) {
if (l < r) {
left = std::min(left, l);
right = std::max(right, r);
last_left = std::max(last_left, l);
++count;
}
}
int span = count == 0 ? 0 : right - left;
int left_span = count == 0 ? 0 : last_left - left;
// Balance persistent right scans against temporary left additions.
int bs = std::max(1, int(std::sqrt(double(span) * left_span /
std::max(1, count))));
int nb = left_span / 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];
// Empty queries may lie outside the span of all nonempty queries.
int blk = l == r ? 0 : (l - left) / bs;
int br = l == r
? r
: left + int(std::min<long long>(span, (blk + 1LL) * 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;
});
// Start the shared state at this group's largest left endpoint.
int base = 0;
for (int id : ord) base = std::max(base, qs[id].first);
int r = base;
for (int id : ord) {
auto [ql, qr] = qs[id];
while (r < qr) {
add(r++);
}
auto tok = ss();
for (int pos = base - 1; pos >= ql; pos--) {
add(pos);
}
ans(id);
rb(tok);
}
rb(a0);
}
}
};
} // namespace noya
// NOYA_ROLLBACK_MO_HPP
#ifndef NOYA_ROLLBACK_MO_HPP
#define NOYA_ROLLBACK_MO_HPP 1
/// @complexity Time: O(Q log(Q+1)) sorting and O(N sqrt(Q) + Q) add/undo steps.
/// Callback costs apply to these steps. Space: O(Q) scheduler storage.
#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).
/// Answers must depend on the included positions, not their insertion order.
/// The caller's initial state is restored before run() returns.
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 left = n, right = 0, last_left = 0, count = 0;
for (auto [l, r] : qs) {
if (l < r) {
left = std::min(left, l);
right = std::max(right, r);
last_left = std::max(last_left, l);
++count;
}
}
int span = count == 0 ? 0 : right - left;
int left_span = count == 0 ? 0 : last_left - left;
// Balance persistent right scans against temporary left additions.
int bs = std::max(1, int(std::sqrt(double(span) * left_span /
std::max(1, count))));
int nb = left_span / 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];
// Empty queries may lie outside the span of all nonempty queries.
int blk = l == r ? 0 : (l - left) / bs;
int br = l == r
? r
: left + int(std::min<long long>(span, (blk + 1LL) * 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;
});
// Start the shared state at this group's largest left endpoint.
int base = 0;
for (int id : ord) base = std::max(base, qs[id].first);
int r = base;
for (int id : ord) {
auto [ql, qr] = qs[id];
while (r < qr) {
add(r++);
}
auto tok = ss();
for (int pos = base - 1; pos >= ql; pos--) {
add(pos);
}
ans(id);
rb(tok);
}
rb(a0);
}
}
};
} // namespace noya
#endif // NOYA_ROLLBACK_MO_HPP
/// @complexity Time: O(Q log(Q+1)) sorting and O(N sqrt(Q) + Q) add/undo steps.
/// Callback costs apply to these steps. Space: O(Q) scheduler storage.
#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).
/// Answers must depend on the included positions, not their insertion order.
/// The caller's initial state is restored before run() returns.
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 left = n, right = 0, last_left = 0, count = 0;
for (auto [l, r] : qs) {
if (l < r) {
left = std::min(left, l);
right = std::max(right, r);
last_left = std::max(last_left, l);
++count;
}
}
int span = count == 0 ? 0 : right - left;
int left_span = count == 0 ? 0 : last_left - left;
// Balance persistent right scans against temporary left additions.
int bs = std::max(1, int(std::sqrt(double(span) * left_span /
std::max(1, count))));
int nb = left_span / 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];
// Empty queries may lie outside the span of all nonempty queries.
int blk = l == r ? 0 : (l - left) / bs;
int br = l == r
? r
: left + int(std::min<long long>(span, (blk + 1LL) * 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;
});
// Start the shared state at this group's largest left endpoint.
int base = 0;
for (int id : ord) base = std::max(base, qs[id].first);
int r = base;
for (int id : ord) {
auto [ql, qr] = qs[id];
while (r < qr) {
add(r++);
}
auto tok = ss();
for (int pos = base - 1; pos >= ql; pos--) {
add(pos);
}
ans(id);
rb(tok);
}
rb(a0);
}
}
};
} // namespace noya
// NOYA_ROLLBACK_MO_HPP