mo.hpp¶
把静态区间询问重排，使左右端点移动总量较小；适合能在增删一个元素时维护答案的离线查询。
Complexity: Time: \(O(Q \log (Q + 1))\) sorting and \(O(N \sqrt{Q} + Q)\) window steps. Space: \(O(Q)\).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(Q log(Q+1)) sorting and O(N sqrt(Q) + Q) window steps.
/// 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>> qs;
mo() = default;
explicit mo(int n_) : n(n_) { assert(n >= 0); }
/// @brief Append [l, r) and return its query id.
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;
}
/// @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 al, AddRight ar, RemoveLeft dl, RemoveRight dr,
Answer ans) const {
int q = int(qs.size());
if (q == 0) {
return;
}
int bs = std::max(1, int(n / std::max(1.0, std::sqrt(double(q)))));
std::vector<int> ord(q);
std::iota(ord.begin(), ord.end(), 0);
std::vector<std::pair<int, int>> key(q);
for (int i = 0; i < q; ++i) {
int block = qs[i].first / bs;
key[i] = {block, (block & 1) ? -qs[i].second : qs[i].second};
}
std::sort(ord.begin(), ord.end(),
[&](int a, int b) { return key[a] < key[b]; });
int l = 0;
int r = 0;
for (int id : ord) {
auto [ql, qr] = qs[id];
while (ql < l) {
al(--l);
}
while (r < qr) {
ar(r++);
}
while (l < ql) {
dl(l++);
}
while (qr < r) {
dr(--r);
}
ans(id);
}
}
};
} // namespace noya
// NOYA_MO_HPP
#ifndef NOYA_MO_HPP
#define NOYA_MO_HPP 1
/// @complexity Time: O(Q log(Q+1)) sorting and O(N sqrt(Q) + Q) window steps.
/// 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>> qs;
mo() = default;
explicit mo(int n_) : n(n_) { assert(n >= 0); }
/// @brief Append [l, r) and return its query id.
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;
}
/// @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 al, AddRight ar, RemoveLeft dl, RemoveRight dr,
Answer ans) const {
int q = int(qs.size());
if (q == 0) {
return;
}
int bs = std::max(1, int(n / std::max(1.0, std::sqrt(double(q)))));
std::vector<int> ord(q);
std::iota(ord.begin(), ord.end(), 0);
std::vector<std::pair<int, int>> key(q);
for (int i = 0; i < q; ++i) {
int block = qs[i].first / bs;
key[i] = {block, (block & 1) ? -qs[i].second : qs[i].second};
}
std::sort(ord.begin(), ord.end(),
[&](int a, int b) { return key[a] < key[b]; });
int l = 0;
int r = 0;
for (int id : ord) {
auto [ql, qr] = qs[id];
while (ql < l) {
al(--l);
}
while (r < qr) {
ar(r++);
}
while (l < ql) {
dl(l++);
}
while (qr < r) {
dr(--r);
}
ans(id);
}
}
};
} // namespace noya
#endif // NOYA_MO_HPP
/// @complexity Time: O(Q log(Q+1)) sorting and O(N sqrt(Q) + Q) window steps.
/// 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>> qs;
mo() = default;
explicit mo(int n_) : n(n_) { assert(n >= 0); }
/// @brief Append [l, r) and return its query id.
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;
}
/// @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 al, AddRight ar, RemoveLeft dl, RemoveRight dr,
Answer ans) const {
int q = int(qs.size());
if (q == 0) {
return;
}
int bs = std::max(1, int(n / std::max(1.0, std::sqrt(double(q)))));
std::vector<int> ord(q);
std::iota(ord.begin(), ord.end(), 0);
std::vector<std::pair<int, int>> key(q);
for (int i = 0; i < q; ++i) {
int block = qs[i].first / bs;
key[i] = {block, (block & 1) ? -qs[i].second : qs[i].second};
}
std::sort(ord.begin(), ord.end(),
[&](int a, int b) { return key[a] < key[b]; });
int l = 0;
int r = 0;
for (int id : ord) {
auto [ql, qr] = qs[id];
while (ql < l) {
al(--l);
}
while (r < qr) {
ar(r++);
}
while (l < ql) {
dl(l++);
}
while (qr < r) {
dr(--r);
}
ans(id);
}
}
};
} // namespace noya
// NOYA_MO_HPP