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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include <bits/stdc++.h>
#define MAX_N 100010
using namespace std;
char ch_buffer;
bool signum;
inline void readInt(int &l) {
l = 0;
do
ch_buffer = cin.get();
while ((ch_buffer < '0' || ch_buffer > '9') && ch_buffer != '0' &&
ch_buffer != '-');
if (ch_buffer == '-') ch_buffer = cin.get(), signum = true;
while (ch_buffer <= '9' && ch_buffer >= '0')
l = (l << 3) + (l << 1) + ch_buffer - '0', ch_buffer = cin.get();
if (signum) l = -l, signum = false;
}
template <class T>
class SegmentTree {
public:
int capacity;
struct node {
T sum_val;
int tag;
node() : sum_val(0), tag(0) {}
};
node *segNode;
inline void updata(int v) {
segNode[v].sum_val =
segNode[v << 1].sum_val + segNode[v << 1 | 1].sum_val;
}
inline void downtag(int v, int s, int t) {
segNode[v << 1].tag += segNode[v].tag;
segNode[v << 1 | 1].tag += segNode[v].tag;
int mid = (s + t) >> 1;
segNode[v << 1].sum_val += segNode[v].tag * (mid - s + 1);
segNode[v << 1 | 1].sum_val += segNode[v].tag * (t - mid);
segNode[v].tag = 0;
}
void modify(int v, int s, int t, int l, int r, T x) {
if (s >= l && t <= r) {
segNode[v].tag += x;
segNode[v].sum_val += x * (t - s + 1);
return;
}
int mid = (s + t) >> 1;
downtag(v, s, t);
if (mid >= l) modify(v << 1, s, mid, l, r, x);
if (mid + 1 <= r) modify(v << 1 | 1, mid + 1, t, l, r, x);
updata(v);
}
inline T get(int v, int s, int t, int l, int r) {
return getSum(v, s, t, l, r);
}
T getSum(int v, int s, int t, int l, int r) {
if (s >= l && t <= r) return segNode[v].sum_val;
int mid = (s + t) >> 1;
T ans = 0;
downtag(v, s, t);
if (mid >= l) ans += getSum(v << 1, s, mid, l, r);
if (mid + 1 <= r) ans += getSum(v << 1 | 1, mid + 1, t, l, r);
updata(v);
return ans;
}
SegmentTree(int n) : capacity(n << 2), segNode(new node[capacity]){};
~SegmentTree() { delete[] segNode; };
};
int n, m;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
readInt(n), readInt(m);
SegmentTree<int> st(n + 10);
int l, r, p;
while (m--) {
if (cin.get() ^ '2') {
readInt(l), readInt(r);
st.modify(1, 1, n, l, r, 1);
} else {
readInt(p);
cout << st.get(1, 1, n, p, p) % 2 << "\n";
}
}
return 0;
}
|
