目录
显示
题目链接
题解
根据异或运算的性质,一个数如果参与了异或运算奇数次,它才会对结果做出贡献。
所以我们先来探究一下一个区间内所有子区间的异或和的异或和中,有哪些数会对答案产生贡献。
容易发现:如果区间左右端点奇偶性不同,则所有数都会在最终答案中被异或偶数次,结果自然为零;如果区间左右端点奇偶性相同,则与区间端点奇偶性相同的位置上的数会被异或奇数次,从而对答案产生贡献,而其余位置则会被异或偶数次,不会对答案产生贡献。
于是问题变成了一个单点修改+区间异或和的问题,而这类问题正是树状数组最擅长的。
#include <cstdio> int n,q,a[200005],b[2][200005]; int lowbit(int x) { return x&(-x); } void add(int x,int pos,int q) { while(pos<=n) { b[q][pos]^=x; pos+=lowbit(pos); } } int query(int pos,int q) { int ans=0; while(pos) { ans^=b[q][pos]; pos-=lowbit(pos); } return ans; } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); add(a[i],i,i&1); } while(q--) { int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==1)add(a[x],x,x&1),add(a[x]=y,x,x&1); else { if((x+y)&1)puts("0"); else printf("%d\n",query(y,x&1)^query(x-1,x&1)); } } return 0; }