# D. Xenia and Bit Operations

Jan 30th, 2021 (edited)
162
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. int tree[2*(1<<17)];
6. int ar[1<<17];
7. int n, m, N;
8.
9. int comb(int a, int b, int level){
10.     if((N - level) % 2 == 0)
11.         return a | b;
12.     return a ^ b;
13. }
14.
15. int build(int i, int l, int r, int level){
16.     if(r == l)
17.         return tree[i] = ar[l];
18.     int mid = (l + r) / 2;
19.     return tree[i] = comb(build(2*i, l, mid, level+1), build(2*i+1, mid+1, r, level+1), level);
20. }
21.
22. int query(int i, int l, int r, int p, int b, int level){
23.     if(r == l)
24.         return tree[i] = b;
25.     int mid = (l + r) / 2;
26.     if(p <= mid)
27.         return tree[i] = comb(query(2*i, l, mid, p, b, level+1), tree[2*i+1], level);
28.     else
29.         return tree[i] = comb(query(2*i+1, mid+1, r, p, b, level+1), tree[2*i], level);
30. }
31.
32. int main(){
33.
34.     scanf("%d%d", &n, &m);
35.
36.     N = n;
37.     n = 1 << n;
38.
39.     for(int i=0;i<n;i++){
40.         scanf("%d", &ar[i]);
41.     }
42.
43.     build(1, 0, n-1, 1);
44.
45.     /*for(int i=1;i<2*n;i++){
46.         printf("%d ", tree[i]);
47.     }*/
48.
49.     for(int i=1;i<=m;i++){
50.         int p, b;
51.         scanf("%d%d", &p, &b);
52.         printf("%d\n", query(1, 0, n, p, b, 1));
53.     }
54.
55.     return 0;
56. }