[loj 3195]「eJOI2019」异或橙子

题目链接

https://loj.ac/problem/3195

题解

根据异或运算的性质，一个数如果参与了异或运算奇数次，它才会对结果做出贡献。

所以我们先来探究一下一个区间内所有子区间的异或和的异或和中，有哪些数会对答案产生贡献。

容易发现：如果区间左右端点奇偶性不同，则所有数都会在最终答案中被异或偶数次，结果自然为零；如果区间左右端点奇偶性相同，则与区间端点奇偶性相同的位置上的数会被异或奇数次，从而对答案产生贡献，而其余位置则会被异或偶数次，不会对答案产生贡献。

于是问题变成了一个单点修改+区间异或和的问题，而这类问题正是树状数组最擅长的。

#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;
}