mo_with_updates.hpp¶
Three-dimensional Mo scheduler for offline range queries mixed with point updates; callbacks own the array and aggregate state.
把区间询问与单点修改一起按三维 Mo 顺序处理；适合可增删元素且可前进、回退修改的离线题。
Implementation¶
#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 left = 0;
int right = 0;
int time = 0;
};
int n = 0;
int update_count = 0;
std::vector<query> queries;
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 update_count++; }
/// @brief Append [left, right) at the current update time and return its id.
int add_query(int left, int right) {
assert(0 <= left && left <= right && right <= n);
int id = int(queries.size());
queries.push_back({left, right, update_count});
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 add_left, AddRight add_right, RemoveLeft remove_left,
RemoveRight remove_right, ApplyUpdate apply_update,
RollbackUpdate rollback_update, Answer answer) const {
if (queries.empty()) {
return;
}
int block_size = std::max(1, int(std::pow(std::max(1, n), 2.0 / 3.0)));
std::vector<int> order(queries.size());
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(), [&](int first, int second) {
const query &a = queries[first];
const query &b = queries[second];
int block_a = a.left / block_size;
int block_b = b.left / block_size;
if (block_a != block_b) {
return block_a < block_b;
}
int right_a = a.right / block_size;
int right_b = b.right / block_size;
if (right_a != right_b) {
return (block_a & 1) ? right_a > right_b : right_a < right_b;
}
return ((block_a ^ right_a) & 1) ? a.time > b.time : a.time < b.time;
});
int left = 0;
int right = 0;
int time = 0;
for (int id : order) {
const query &target = queries[id];
while (time < target.time) {
apply_update(time++, left, right);
}
while (target.time < time) {
rollback_update(--time, left, right);
}
while (target.left < left) {
add_left(--left);
}
while (right < target.right) {
add_right(right++);
}
while (left < target.left) {
remove_left(left++);
}
while (target.right < right) {
remove_right(--right);
}
answer(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 left = 0;
int right = 0;
int time = 0;
};
int n = 0;
int update_count = 0;
std::vector<query> queries;
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 update_count++; }
/// @brief Append [left, right) at the current update time and return its id.
int add_query(int left, int right) {
assert(0 <= left && left <= right && right <= n);
int id = int(queries.size());
queries.push_back({left, right, update_count});
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 add_left, AddRight add_right, RemoveLeft remove_left,
RemoveRight remove_right, ApplyUpdate apply_update,
RollbackUpdate rollback_update, Answer answer) const {
if (queries.empty()) {
return;
}
int block_size = std::max(1, int(std::pow(std::max(1, n), 2.0 / 3.0)));
std::vector<int> order(queries.size());
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(), [&](int first, int second) {
const query &a = queries[first];
const query &b = queries[second];
int block_a = a.left / block_size;
int block_b = b.left / block_size;
if (block_a != block_b) {
return block_a < block_b;
}
int right_a = a.right / block_size;
int right_b = b.right / block_size;
if (right_a != right_b) {
return (block_a & 1) ? right_a > right_b : right_a < right_b;
}
return ((block_a ^ right_a) & 1) ? a.time > b.time : a.time < b.time;
});
int left = 0;
int right = 0;
int time = 0;
for (int id : order) {
const query &target = queries[id];
while (time < target.time) {
apply_update(time++, left, right);
}
while (target.time < time) {
rollback_update(--time, left, right);
}
while (target.left < left) {
add_left(--left);
}
while (right < target.right) {
add_right(right++);
}
while (left < target.left) {
remove_left(left++);
}
while (target.right < right) {
remove_right(--right);
}
answer(id);
}
}
};
} // namespace noya