学海泛舟

codeforces contest339 D Xenia and Bit Operations 题解

发表于 | 分类于 |

原题

传送门

题目大意

给出一串长为$2^n$的数字串，先将相邻的两个数字按位或，得到$2^{n-1}$的数字，再进行按位异或，反复进行这样的操作，直到只剩下唯一的数字。给出m个询问，每次将一个位置上的数字改成指定的数字，求最后得到的数字。

分析

这是一个单点修改区间求值的问题，可以使用线段树，只是合并的时候注意一下，需要对两个子区间的值或还是异或即可。

参考代码

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
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;
int fun(int n,int k){
    int res=1;
    while(k){
        if(k&1) res*=n;
        n*=n;
        k>>=1;
    }
    return res;
}
int a[420000];
map<int,bool> mp;
void build(int root,int l,int r){
    if(l==r){
        scanf("%d",&a[root]);
        return ;
    }
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
    if(mp[r-l+1]==1){
        a[root]=(a[root<<1]|a[root<<1|1]);
    } else {
        a[root]=(a[root<<1]^a[root<<1|1]);
    }
}
int query(int root,int l,int r,int x,int y){
    if(x<=l&&y>=r){
        return a[root];
    }
    int mid=(l+r)>>1;
    int ans1=-1;
    int ans2=-1;
    if(x<=mid) ans1=query(root<<1,l,mid,x,y);
    if(y>mid) ans2=query(root<<1|1,mid+1,r,x,y);
    if(ans1!=-1&&ans2!=-1){
        if(mp[r-l+1]==1){
            int ans=(ans1|ans2);
            return ans;
        } else {
            int ans=(ans1^ans2);
            return ans;
        }
    } else if(ans1!=-1){
        return ans1;
    } else if(ans2!=-1){
        return ans2;
    }
}
void change(int root,int l,int r,int x,int y){
    if(l==r){
        a[root]=y;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid) {
        change(root<<1,l,mid,x,y);
    } else {
        change(root<<1|1,mid+1,r,x,y);
    }
    if(mp[r-l+1]==1){
        a[root]=(a[root<<1]|a[root<<1|1]);
    } else {
        a[root]=(a[root<<1]^a[root<<1|1]);
    }
}
void init(){
    mp.clear();
    int res=1;
    mp[res]=0;
    for(int i=1;i<=17;++i){
        res*=2;
        mp[res]=(i%2);
    }
}
int main(){
    int n,m;
    init();
    scanf("%d %d",&n,&m);
    int r=fun(2,n);
    build(1,1,r);
    while(m--){
        int p,b;
        scanf("%d %d",&p,&b);
        change(1,1,r,p,b);
        int ans=query(1,1,r,1,r);
        printf("%d\n",ans);
    }
    return 0;
}