mo.hpp¶
Mo's algorithm for offline half-open range queries.
把静态区间询问重排，使左右端点移动总量较小；适合能在增删一个元素时维护答案的离线查询。
Implementation¶
#ifndef NOYA_MO_HPP
#define NOYA_MO_HPP 1
/// @complexity Time: O((N + Q) sqrt(N)) add/remove steps with standard block ordering.
/// Space: O(Q).
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Mo's algorithm for offline half-open range queries.
struct mo {
int n = 0;
std::vector<std::pair<int, int>> queries;
mo() = default;
explicit mo(int n_) : n(n_) { assert(n >= 0); }
/// @brief Append [left, right) and return its query id.
int add_query(int left, int right) {
assert(0 <= left && left <= right && right <= n);
int id = int(queries.size());
queries.emplace_back(left, right);
return id;
}
/// @brief Move one shared window through all queries and call answer(id)
/// after the corresponding range is active.
template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight,
class Answer>
void run(AddLeft add_left, AddRight add_right, RemoveLeft remove_left,
RemoveRight remove_right, Answer answer) const {
int query_count = int(queries.size());
if (query_count == 0) {
return;
}
int block_size =
std::max(1, int(n / std::max(1.0, std::sqrt(double(query_count)))));
std::vector<int> order(query_count);
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(), [&](int first, int second) {
int first_block = queries[first].first / block_size;
int second_block = queries[second].first / block_size;
if (first_block != second_block) {
return first_block < second_block;
}
if (first_block & 1) {
return queries[first].second > queries[second].second;
}
return queries[first].second < queries[second].second;
});
int left = 0;
int right = 0;
for (int id : order) {
auto [query_left, query_right] = queries[id];
while (query_left < left) {
add_left(--left);
}
while (right < query_right) {
add_right(right++);
}
while (left < query_left) {
remove_left(left++);
}
while (query_right < right) {
remove_right(--right);
}
answer(id);
}
}
};
} // namespace noya
#endif // NOYA_MO_HPP
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <utility>
#include <vector>
/// @complexity Time: O((N + Q) sqrt(N)) add/remove steps with standard block ordering.
/// Space: O(Q).
namespace noya {
/// @brief Mo's algorithm for offline half-open range queries.
struct mo {
int n = 0;
std::vector<std::pair<int, int>> queries;
mo() = default;
explicit mo(int n_) : n(n_) { assert(n >= 0); }
/// @brief Append [left, right) and return its query id.
int add_query(int left, int right) {
assert(0 <= left && left <= right && right <= n);
int id = int(queries.size());
queries.emplace_back(left, right);
return id;
}
/// @brief Move one shared window through all queries and call answer(id)
/// after the corresponding range is active.
template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight,
class Answer>
void run(AddLeft add_left, AddRight add_right, RemoveLeft remove_left,
RemoveRight remove_right, Answer answer) const {
int query_count = int(queries.size());
if (query_count == 0) {
return;
}
int block_size =
std::max(1, int(n / std::max(1.0, std::sqrt(double(query_count)))));
std::vector<int> order(query_count);
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(), [&](int first, int second) {
int first_block = queries[first].first / block_size;
int second_block = queries[second].first / block_size;
if (first_block != second_block) {
return first_block < second_block;
}
if (first_block & 1) {
return queries[first].second > queries[second].second;
}
return queries[first].second < queries[second].second;
});
int left = 0;
int right = 0;
for (int id : order) {
auto [query_left, query_right] = queries[id];
while (query_left < left) {
add_left(--left);
}
while (right < query_right) {
add_right(right++);
}
while (left < query_left) {
remove_left(left++);
}
while (query_right < right) {
remove_right(--right);
}
answer(id);
}
}
};
} // namespace noya