洛谷 P5057 [CQOI2006]简单题 (树状数组,位运算)

题意:有一个长度为\(n\)的数组,进行\(m\)次操作,每次读入一个值\(t\),如果\(t=1\),则将区间\([l,r]\)的数字反转,若\(t=2\),则查询下标为\(i\)的值.

题解:树状数组的板子题,但是考察到了位运算的知识,我们对区间进行反转的时候,只需要对树状数组\(c[l]\) ^ 1,\(c[r+1]\) ^ \(1\)即可,然后进行单点查询时只须对前缀异或就好了.

代码:

int n,m;
int a[N];
int op,l,r,x;int lowbit(int x){
return x&(-x);
}void updata(int i){
while(i<=n){
a[i]^=1;
i+=lowbit(i);
}
}int get_sum(int i){
int res=0;
while(i>0){
res^=a[i];
i-=lowbit(i);
}
return res;
}int main() {
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=read();
m=read();
while(m--){
op=read();
if(op==1){
l=read();
r=read();
updata(l);
updata(r+1);
}
else{
x=read();
printf("%d\n",get_sum(x));
}
}    return 0;
}