mo_with_updates.hpp¶
把区间询问与单点修改一起按三维 Mo 顺序处理；适合可增删元素且可前进、回退修改的离线题。
Complexity: Time: O((N + Q) N^(2/3)) range/time moves with standard blocking. Space: O(N + Q).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((N + Q) N^(2/3)) range/time moves with standard blocking.
/// Space: O(N + Q).
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <tuple>
#include <vector>
namespace noya {
/// @brief Three-dimensional Mo scheduler for offline range queries mixed with
/// point updates; callbacks own the array and aggregate state.
struct mo_with_updates {
struct query {
int l = 0;
int r = 0;
int t = 0;
};
int n = 0;
int nu = 0;
std::vector<query> qs;
mo_with_updates() = default;
explicit mo_with_updates(int n_) : n(n_) { assert(n >= 0); }
/// @brief Record one update in chronological order and return its id.
int add_update() { return nu++; }
/// @brief Append [l, r) at the current update time and return its id.
int add_query(int l, int r) {
assert(0 <= l && l <= r && r <= n);
int id = int(qs.size());
qs.push_back({l, r, nu});
return id;
}
/// @brief Process queries while moving a range and time cursor. The update
/// callbacks receive (update_id, current_left, current_right).
template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight,
class ApplyUpdate, class RollbackUpdate, class Answer>
void run(AddLeft al, AddRight ar, RemoveLeft dl,
RemoveRight dr, ApplyUpdate ap,
RollbackUpdate un, Answer ans) const {
if (qs.empty()) {
return;
}
int bs = std::max(1, int(std::pow(std::max(1, n), 2.0 / 3.0)));
std::vector<int> ord(qs.size());
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int arr, int B) {
const query &a = qs[arr];
const query &b = qs[B];
int ba = a.l / bs;
int bb = b.l / bs;
if (ba != bb) {
return ba < bb;
}
int ra = a.r / bs;
int rb = b.r / bs;
if (ra != rb) {
return (ba & 1) ? ra > rb : ra < rb;
}
return ((ba ^ ra) & 1) ? a.t > b.t : a.t < b.t;
});
int l = 0;
int r = 0;
int t = 0;
for (int id : ord) {
const query &tar = qs[id];
while (t < tar.t) {
ap(t++, l, r);
}
while (tar.t < t) {
un(--t, l, r);
}
while (tar.l < l) {
al(--l);
}
while (r < tar.r) {
ar(r++);
}
while (l < tar.l) {
dl(l++);
}
while (tar.r < r) {
dr(--r);
}
ans(id);
}
}
};
} // namespace noya
#ifndef NOYA_MO_WITH_UPDATES_HPP
#define NOYA_MO_WITH_UPDATES_HPP 1
/// @complexity Time: O((N + Q) N^(2/3)) range/time moves with standard blocking.
/// Space: O(N + Q).
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <tuple>
#include <vector>
namespace noya {
/// @brief Three-dimensional Mo scheduler for offline range queries mixed with
/// point updates; callbacks own the array and aggregate state.
struct mo_with_updates {
struct query {
int l = 0;
int r = 0;
int t = 0;
};
int n = 0;
int nu = 0;
std::vector<query> qs;
mo_with_updates() = default;
explicit mo_with_updates(int n_) : n(n_) { assert(n >= 0); }
/// @brief Record one update in chronological order and return its id.
int add_update() { return nu++; }
/// @brief Append [l, r) at the current update time and return its id.
int add_query(int l, int r) {
assert(0 <= l && l <= r && r <= n);
int id = int(qs.size());
qs.push_back({l, r, nu});
return id;
}
/// @brief Process queries while moving a range and time cursor. The update
/// callbacks receive (update_id, current_left, current_right).
template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight,
class ApplyUpdate, class RollbackUpdate, class Answer>
void run(AddLeft al, AddRight ar, RemoveLeft dl,
RemoveRight dr, ApplyUpdate ap,
RollbackUpdate un, Answer ans) const {
if (qs.empty()) {
return;
}
int bs = std::max(1, int(std::pow(std::max(1, n), 2.0 / 3.0)));
std::vector<int> ord(qs.size());
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int arr, int B) {
const query &a = qs[arr];
const query &b = qs[B];
int ba = a.l / bs;
int bb = b.l / bs;
if (ba != bb) {
return ba < bb;
}
int ra = a.r / bs;
int rb = b.r / bs;
if (ra != rb) {
return (ba & 1) ? ra > rb : ra < rb;
}
return ((ba ^ ra) & 1) ? a.t > b.t : a.t < b.t;
});
int l = 0;
int r = 0;
int t = 0;
for (int id : ord) {
const query &tar = qs[id];
while (t < tar.t) {
ap(t++, l, r);
}
while (tar.t < t) {
un(--t, l, r);
}
while (tar.l < l) {
al(--l);
}
while (r < tar.r) {
ar(r++);
}
while (l < tar.l) {
dl(l++);
}
while (tar.r < r) {
dr(--r);
}
ans(id);
}
}
};
} // namespace noya
#endif // NOYA_MO_WITH_UPDATES_HPP
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <tuple>
#include <vector>
/// @complexity Time: O((N + Q) N^(2/3)) range/time moves with standard blocking.
/// Space: O(N + Q).
namespace noya {
/// @brief Three-dimensional Mo scheduler for offline range queries mixed with
/// point updates; callbacks own the array and aggregate state.
struct mo_with_updates {
struct query {
int l = 0;
int r = 0;
int t = 0;
};
int n = 0;
int nu = 0;
std::vector<query> qs;
mo_with_updates() = default;
explicit mo_with_updates(int n_) : n(n_) { assert(n >= 0); }
/// @brief Record one update in chronological order and return its id.
int add_update() { return nu++; }
/// @brief Append [l, r) at the current update time and return its id.
int add_query(int l, int r) {
assert(0 <= l && l <= r && r <= n);
int id = int(qs.size());
qs.push_back({l, r, nu});
return id;
}
/// @brief Process queries while moving a range and time cursor. The update
/// callbacks receive (update_id, current_left, current_right).
template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight,
class ApplyUpdate, class RollbackUpdate, class Answer>
void run(AddLeft al, AddRight ar, RemoveLeft dl,
RemoveRight dr, ApplyUpdate ap,
RollbackUpdate un, Answer ans) const {
if (qs.empty()) {
return;
}
int bs = std::max(1, int(std::pow(std::max(1, n), 2.0 / 3.0)));
std::vector<int> ord(qs.size());
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int arr, int B) {
const query &a = qs[arr];
const query &b = qs[B];
int ba = a.l / bs;
int bb = b.l / bs;
if (ba != bb) {
return ba < bb;
}
int ra = a.r / bs;
int rb = b.r / bs;
if (ra != rb) {
return (ba & 1) ? ra > rb : ra < rb;
}
return ((ba ^ ra) & 1) ? a.t > b.t : a.t < b.t;
});
int l = 0;
int r = 0;
int t = 0;
for (int id : ord) {
const query &tar = qs[id];
while (t < tar.t) {
ap(t++, l, r);
}
while (tar.t < t) {
un(--t, l, r);
}
while (tar.l < l) {
al(--l);
}
while (r < tar.r) {
ar(r++);
}
while (l < tar.l) {
dl(l++);
}
while (tar.r < r) {
dr(--r);
}
ans(id);
}
}
};
} // namespace noya