#505. 动态区间异或和
统计 描述 提交 自定义测试 【题目描述】： 给定一个由n个正整数组成的序列 {a1 ,a2 , … ,an a1 ,a2 , … ,an }。
两种操作：
1 x y：表示将 axax的值改为y；
2 x y：表示询问区间[x,y]的异或和；
【输入描述】： 第一行，两个正整数n和m，用空格隔开。
第二行，n个正整数表示序列{a1 ,a2 , … ,an a1 ,a2 , … ,an }。
以下m行，每行三个数，表示一个操作，格式如题面。
【输出描述】： 对于每个操作2询问占一行一个整数。
【样例输入】： 10 10 1 9 7 8 10 9 7 7 3 2 1 10 3 1 7 2 2 3 8 1 6 4 1 3 5 1 9 9 2 4 9 1 3 9 2 2 8 1 8 5 【样例输出】： 9 10 3 【时间限制、数据范围及描述】： 时间：1s 空间：64M
对于40%的数据：1<=n,m<=10000
对于100%的数据：1<=n,m<=200,000
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <queue> #include <stack> #include <cmath> using namespace std; const int MAXN=500005; int n,m,a[MAXN],c[MAXN],k,x,y,z; int look(int u){return u&(-u);} void work(int u,int v,int kk){ for(int i=u;i<=n;i+=look(i)) c[i]^=v^kk; } int getsum(int u){ int ans=c[u]; for(int i=u-look(u);i>0;i-=look(i)) ans^=c[i]; return ans; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++){ k=look(i);c[i]=a[i]; for(int j=1;j<k;j++) c[i]^=a[i-k+j]; } while(m--){ scanf("%d%d%d",&x,&y,&z); if(x==1) {work(y,z,a[y]);a[y]=z;} if(x==2) printf("%d\n",getsum(z)^getsum(y-1)); } return 0; }