/
mo.hpp
39 lines (35 loc) · 1.2 KB
/
mo.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* @brief Mo's Algorithm
*/
struct Mo {
int n;
vector<pair<int, int> > lr;
explicit Mo(int n) : n(n) {}
void add(int l, int r) { /* [l, r) */ lr.emplace_back(l, r); }
template <typename AL, typename AR, typename EL, typename ER, typename O>
void build(const AL &add_left, const AR &add_right, const EL &erase_left,
const ER &erase_right, const O &out) {
int q = (int)lr.size();
int bs = n / min<int>(n, sqrt(q));
vector<int> ord(q);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), [&](int a, int b) {
int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
if (ablock != bblock) return ablock < bblock;
return (ablock & 1) ? lr[a].second > lr[b].second
: lr[a].second < lr[b].second;
});
int l = 0, r = 0;
for (auto idx : ord) {
while (l > lr[idx].first) add_left(--l);
while (r < lr[idx].second) add_right(r++);
while (l < lr[idx].first) erase_left(l++);
while (r > lr[idx].second) erase_right(--r);
out(idx);
}
}
template <typename A, typename E, typename O>
void build(const A &add, const E &erase, const O &out) {
build(add, add, erase, erase, out);
}
};