动态区间异或和

【题目描述】:

给定一个由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 }

 

上一篇:leetcode 111 二叉树的最小深度


下一篇:递归