-
Notifications
You must be signed in to change notification settings - Fork 0
/
14245.cpp
94 lines (91 loc) · 2.17 KB
/
14245.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
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
91
92
93
94
#include <iostream>
#include <vector>
#define LEFT (node << 1)
#define RIGHT (LEFT + 1)
using ui = unsigned int;
using namespace std;
class SegTree {
private:
vector<ui> tree, lazy;
int N;
inline bool isLeaf(int ns, int ne) {
return ns == ne;
}
inline int intervalSize(int s, int e) {
return e - s + 1;
}
void propagate(int node, int ns, int ne) {
if (!lazy[node]) {
return;
}
if (!isLeaf(ns, ne)) {
lazy[LEFT] ^= lazy[node];
lazy[RIGHT] ^= lazy[node];
}
if (intervalSize(ns, ne) & 1) {
tree[node] ^= lazy[node];
}
lazy[node] = 0;
}
void update(int s, int e, int node, int ns, int ne, ui val) {
if (e < ns || s > ne) {
return;
}
if (s <= ns && ne <= e) {
lazy[node] ^= val;
propagate(node, ns, ne);
return;
}
int m = (ns + ne) >> 1;
update(s, e, LEFT, ns, m, val);
update(s, e, RIGHT ,m + 1, ne, val);
tree[node] = tree[LEFT] ^ tree[RIGHT];
}
int query(int s, int e, int node, int ns, int ne) {
propagate(node, ns, ne);
if (e < ns || s > ne) {
return 0;
}
if (isLeaf(ns, ne)) {
return tree[node];
}
int m = (ns + ne) >> 1;
return query(s, e, LEFT, ns, m) ^ query(s, e, RIGHT, m + 1, ne);
}
public:
void update(int s, int e, ui val) {
update(s, e, 1, 1, N, val);
}
int query(int s, int e) {
return query(s, e, 1, 1, N);
}
SegTree(int size) : tree(size << 2), lazy(size << 2), N(size) {}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin>>N;
SegTree seg(N);
for (int i = 1; i <= N; i++) {
ui x;
cin>>x;
seg.update(i, i, x);
}
int Q;
cin>>Q;
while (Q--) {
ui t;
cin>>t;
if (t == 1) {
ui a,b,c;
cin>>a>>b>>c;
seg.update(a+1,b+1,c);
} else {
int a;
cin>>a;
cout << seg.query(a+1, a+1) << '\n';
}
}
}