-
Notifications
You must be signed in to change notification settings - Fork 0
/
supercomputer.cpp
57 lines (47 loc) · 1.18 KB
/
supercomputer.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
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
struct Segtree {
int sum_query(int p, int L, int R, int i, int j) {
if (i > R || j < L) return 0;
if (L >= i && R <= j) return tree[p];
return sum_query(left(p), L, (L + R) / 2, i, j) +
sum_query(right(p), (L + R) / 2 + 1, R, i, j);
}
void flip(int p, int L, int R, int pos) {
if (L == R) {
tree[p] = A[pos] = !tree[p];
} else {
int m = (L + R) / 2;
if (pos <= m)
flip(left(p), L, m, pos);
else
flip(right(p), m + 1, R, pos);
tree[p] = tree[left(p)] + tree[right(p)];
}
}
Segtree(short* arr, int _n) : n(_n), A(arr) { tree.assign(4 * n, 0); }
private:
vector<int> tree;
int n;
short* A;
inline int left(int p) { return p << 1; }
inline int right(int p) { return (p << 1) + 1; }
};
short bits[1'000'001];
int N, Q;
int main() {
cin >> N >> Q;
Segtree st(bits, N);
while (Q--) {
char query_type;
int i, j;
scanf(" %c", &query_type);
if (query_type == 'F') {
scanf("%d", &i);
st.flip(1, 0, N - 1, i - 1);
} else {
scanf("%d %d", &i, &j);
printf("%d\n", st.sum_query(1, 0, N - 1, i - 1, j - 1));
}
}
}