【UOJ 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

  题解：咳咳咳速度赛，但最后没搞出来，暴力了40分。枯了我 补充知识点！！！a^b^a=b; 先奉上40分代码： #include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> typedef long long ll; using namespace std; const int N=200003; int n,m,a,b,w,c[N]; inline int get(){ int f=1; char c=getchar(); int res=0; while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); } while (c>='0'&&c<='9'){ res=(res<<3)+(res<<1)+c-'0'; c=getchar(); } return res*f; } int low(int x){ return x&(-x); } void update(int x,int v){ while(x<=n){ c[x]+=v; x+=low(x); } } int sum(int x){ int ans=c[x]; while(x>0){ ans^=c[x]; x-=low(x); } return ans; } int main() { n=get(); m=get(); /*for(int i=1;i<=n;i++){ a=get(); update(i,a); } while(m--){ a=get();b=get();w=get(); if(a==2) printf("%d\n",sum(w)^sum(b-1)); else update(b,w-b); } */ for(int i=1;i<=n;i++) scanf("%d",&c[i]); int o,x,y; while(m--){ scanf("%d %d %d",&o,&x,&y); if(o==1) c[x]=y; else{ int ans=0; for(int i=x;i<=y;i++) ans=ans^c[i]; printf("%d\n",ans); } } return 0; }

 

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11204499.html