mo.hpp¶
把静态区间询问重排，使左右端点移动总量较小；适合能在增删一个元素时维护答案的离线查询。
Complexity: Time: O((N + Q) sqrt(N)) add/remove steps with standard block ordering. Space: O(Q).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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>> 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::sort(ord.begin(), ord.end(), [&](int a, int b) {
int b1 = qs[a].first / bs;
int b2 = qs[b].first / bs;
if (b1 != b2) {
return b1 < b2;
}
if (b1 & 1) {
return qs[a].second > qs[b].second;
}
return qs[a].second < qs[b].second;
});
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
#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>> 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::sort(ord.begin(), ord.end(), [&](int a, int b) {
int b1 = qs[a].first / bs;
int b2 = qs[b].first / bs;
if (b1 != b2) {
return b1 < b2;
}
if (b1 & 1) {
return qs[a].second > qs[b].second;
}
return qs[a].second < qs[b].second;
});
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
#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>> 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::sort(ord.begin(), ord.end(), [&](int a, int b) {
int b1 = qs[a].first / bs;
int b2 = qs[b].first / bs;
if (b1 != b2) {
return b1 < b2;
}
if (b1 & 1) {
return qs[a].second > qs[b].second;
}
return qs[a].second < qs[b].second;
});
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