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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
struct L_B {
ll a[35], w[35];
void clear() {
for (int i = 0; i <= 31; ++i)
a[i] = w[i] = 0;
}
bool insert(ll val, ll k) {
for (int i = 31; i >= 0; --i)
if (val & (1ll << i)) {
if (a[i] == 0) {
a[i] = val;
w[i] = k;
break;
}
val ^= a[i];
}
return val > 0;
}
ll sum() {
ll ret = 0;
for (int i = 0; i <= 31; ++i)
if (a[i]) ret += w[i];
return ret;
}
void print() {
for (int i = 0; i <= 31; ++i)
if (a[i]) printf("%lld ", a[i]);
printf("\n");
}
};
L_B merge(L_B A, L_B B) {
pair<ll, ll> tmp[71];
int cnt = 0;
for (int i = 0; i <= 31; ++i) {
if (A.a[i]) tmp[++cnt].first = A.w[i], tmp[cnt].second = A.a[i];
if (B.a[i]) tmp[++cnt].first = B.w[i], tmp[cnt].second = B.a[i];
}
sort(tmp + 1, tmp + cnt + 1);
L_B ret;
ret.clear();
for (int i = cnt; i >= 1; --i)
ret.insert(tmp[i].second, tmp[i].first);
return ret;
}
int n, q;
pair<ll, ll> a[MAXN];
struct Segment_Tree {
struct Node {
int l, r;
L_B b;
} node[MAXN * 3];
#define b(u) node[u].b
#define lson(u) node[u].l
#define rson(u) node[u].r
int cnt = 0, R = 0;
void build(int& u, int l, int r) {
u = ++cnt;
b(u).clear();
if (l == r) {
b(u).insert(a[l].second, a[l].first);
return;
}
int mid = (l + r) >> 1;
build(lson(u), l, mid), build(rson(u), mid + 1, r);
b(u) = merge(b(lson(u)), b(rson(u)));
}
L_B query(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return b(u);
if (r < ql || l > qr) {
L_B ret;
ret.clear();
return ret;
}
int mid = (l + r) >> 1;
return merge(query(lson(u), l, mid, ql, qr), query(rson(u), mid + 1, r, ql, qr));
}
void modify(int u, int l, int r, int p, ll val, ll k) {
if (l == r) {
b(u).clear();
b(u).insert(val, k);
return;
}
int mid = (l + r) >> 1;
if (p <= mid) modify(lson(u), l, mid, p, val, k);
else modify(rson(u), mid + 1, r, p, val, k);
b(u) = merge(b(lson(u)), b(rson(u)));
}
} T;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld%lld", &a[i].second, &a[i].first);
T.build(T.R, 1, n);
scanf("%d", &q);
while (q--) {
int op;
scanf("%d", &op);
if (op == 0) {
int l, r;
scanf("%d%d", &l, &r);
L_B ans = T.query(T.R, 1, n, l, r);
printf("%lld\n", T.query(T.R, 1, n, l, r).sum());
} else {
int x, a, b;
scanf("%d%d%d", &x, &a, &b);
T.modify(T.R, 1, n, x, a, b);
}
}
return 0;
}
|