【题目描述】:
给定一个由n个正整数组成的序列
两种操作:
1 x y:表示将 axax的值改为y;
2 x y:表示询问区间[x,y]的异或和;
【输入描述】:
第一行,两个正整数n和m,用空格隔开。
第二行,n个正整数表示序列
以下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
【解题思路】
树状数组+异或
关于异或的运算可以百度一下
=GetSum(y)^GetSum(y-1)^z;
这里是一个难点
思想是a^b^a=b
AMAZING!!
其余和树状数组差别不大开,看code
【code】
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 int n,m; 6 int a,c[500005]; 7 inline int lowbit(int x){ 8 return x&(-x); 9 } 10 inline int GetSum(int x){ 11 int ans=0; 12 for(register int i=x;i!=0;i-=lowbit(i)) 13 ans^=c[i]; 14 return ans; 15 } 16 inline void Add(int x,int y){ 17 for(register int i=x;i<=n;i+=lowbit(i)) 18 c[i]^=y; 19 return ; 20 } 21 int main(){ 22 //freopen("3374.in","r",stdin); 23 //freopen("3374.out","w",stdout); 24 scanf("%d%d",&n,&m); 25 for(register int i=1;i<=n;i++){ 26 scanf("%d",&a); 27 Add(i,a); 28 } 29 int x,y,z; 30 for(register int i=1;i<=m;i++){ 31 scanf("%d%d%d",&x,&y,&z); 32 if(x==1){ 33 z=GetSum(y)^GetSum(y-1)^z; 34 Add(y,z); 35 } 36 if(x==2)printf("%d\n",GetSum(z)^GetSum(y-1)); 37 } 38 return 0; 39 }