-
Notifications
You must be signed in to change notification settings - Fork 0
/
sqrt_decomposition_mos_algorithm.cpp
53 lines (53 loc) · 1.2 KB
/
sqrt_decomposition_mos_algorithm.cpp
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
int sq;
struct se {
int s, e, idx;
bool operator<(const se& rhs) const {
if (s / sq != rhs.s / sq) return s / sq < rhs.s / sq;
return e < rhs.e;
}
};
// Zigzag Mo's (faster than basic Mo's Algorithm)
/*struct se {
int s, e, idx;
bool operator<(const se &rhs) const {
if(s / sq != rhs.s / sq) return s / sq < rhs.s / sq;
else return (s / sq) & 1 ? e < rhs.e : e > rhs.e;
}
};*/
vector<se> q;
vector<int> ans;
void input() {
// TODO: 1. receive input 2. resize q, ans 3. calculate sq
}
void add(int idx) {
// TODO: add value at idx from data structure
}
void del(int idx) {
// TODO: remove value at idx from data structure
}
int query() {
// TODO: extract the current answer of the data structure
}
void f() {
int s = q[0].s, e = q[0].e;
// TODO: initialize data structure
ans[q[0].idx] = query();
for (int i = 1; i < q.size(); i++) {
while (q[i].s < s) add(--s);
while (e < q[i].e) add(++e);
while (s < q[i].s) del(s++);
while (q[i].e < e) del(e--);
ans[q[i].idx] = query();
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios_base::sync_with_stdio(false);
input();
sort(q.begin(), q.end());
f();
for (auto& i : ans)
cout << i << '\n';
}