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
| template <typename T>
class SegmentTree {
int n;
vector<T> tree;
T merge_val(T a, T b) const { return a ^ b; } // 合并子树
void maintain(int node) { // 维护整棵树
tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
}
void build(const vector<T>& a, int node, int l, int r) {
if (l == r) {
tree[node] = a[l];
return;
}
int m = (l + r) / 2;
build(a, node * 2, l, m);
build(a, node * 2 + 1, m + 1, r);
maintain(node);
} // 建树
void update(int node, int l, int r, int i, T val) {
if (l == r) {
tree[node] = val;
return;
}
int m = (l + r) / 2;
if (i <= m)
update(node * 2, l, m, i, val);
else
update(node * 2 + 1, m + 1, r, i, val);
maintain(node);
} // 更新i处的值为val
T query(int node, int l, int r, int ql, int qr) const {
if (ql <= l && r <= qr) return tree[node];
int m = (l + r) / 2;
if (qr <= m) return query(node * 2, l, m, ql, qr);
if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
T l_res = query(node * 2, l, m, ql, qr);
T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
return merge_val(l_res, r_res);
} // 查询[ql,qr]的值
int find_first(int node, int l, int r, int ql, int qr, T val) const {
if (r < ql || l > qr) return -1;
if (tree[node] < val) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int res = find_first(node << 1, l, m, ql, qr, val);
if (res != -1) return res;
return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
} // 若遇到固定左端点的情况，需要使用全局变量（或者传入引用）记录前缀分段最大值，加一个被待求区间完全覆盖的剪枝
int find_last(int node, int l, int r, int ql, int qr, T val) const {
if (r < ql || l > qr) return -1;
if (tree[node] < val) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
if (res != -1) return res;
return find_last(node << 1, l, m, ql, qr, val);
}
public:
SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}
SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); } // 传入一个数组维护
void update(int i, T val) { update(1, 0, n - 1, i, val); } // 更新i的值为val
T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); } // 查询[ql,qr]的值
T get(int i) const { return query(1, 0, n - 1, i, i); } // 取出i处的值
int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); } // 查询[ql,qr]中第一个满足条件的下标
int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); } // 查询[ql,qr]中最后一个满足条件的下标
};
void solve() {
int n, q, b, c;
cin >> n >> q;
vector<int> a((1 << n));
for (int i = 0; i <= (1 << n) - 1; i++) cin >> a[i];
SegmentTree tree(a);
for (int i = 1; i <= q; i++) {
cin >> b >> c;
b--;
int tem = a[b];
tree.update(b, c);
int tem2 = b;
int ans = 0;
for (int j = 0; j <= n - 1; j++) {
int tem3 = tem2 >> j;
if (tem3 & 1) {
int pre = tree.query(tem3 << j, (tem3 << j) + (1 << j) - 1);
int pre2 = tree.query((tem3 - 1) << j, (tem3 << j) - 1);
if (pre <= pre2) ans += (1 << j);
} else {
int pre = tree.query(tem3 << j, (tem3 << j) + (1 << j) - 1);
int pre2 = tree.query((tem3 + 1) << j, ((tem3 + 1) << j) + (1 << j) - 1);
if (pre < pre2) ans += (1 << j);
}
}
tree.update(b, tem);
cout << ans << endl;
}
return;
}
|
