<span>2019ICPC南昌邀请赛 Sequence</span>
题意：给出n个点的权值，m次操作，操作为1时为询问，每次询问给出 l 和 r ，求 f(l,r)。操作为0时为修改权值。
f(l,r)=f(l,l)⊕f(l,l+1)⊕⋯⊕f(l,r)⊕f(l+1,l+1)⊕⋯f(l+1,r)⊕⋯⊕f(r,r)F(l,r)=f(l,l)⊕f(l,l+1)⊕⋯⊕f(l,r)⊕f(l+1,l+1)⊕⋯f(l+1,r)⊕⋯⊕f(r,r)。
题解：首先多写算几个 l 到 r，可以发现当 r - l 时奇数的时候，f(l,r)为0；当 r - l 为偶数时，就是 l⊕l+2⊕⋯⊕r；区间异或可以用两个树状数组来完成，一个记录奇数位的前缀异或，一个记录偶数为的前缀异或。修改某个点权值时可以用式子a^b^b=a来更新权值。树状数组异或只要把+改成^就好了。
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back() 4 #define ft first 5 #define sd second 6 using namespace std; 7 8 int a[100100],c[100100],d[100100],n,m; 9 10 int lowbit(int x) 11 { 12 return x&(-x); 13 } 14 15 int sum(int x,int a[]) //区间查询 16 { 17 int s=0; 18 while(x>0) 19 { 20 s^=a[x]; 21 x-=lowbit(x); 22 } 23 return s; 24 } 25 26 void update(int x,int d,int a[]) //单点更新 27 { 28 while(x<=n) 29 { 30 a[x]^=d; 31 x+=lowbit(x); 32 } 33 } 34 35 inline int read() { 36 char ch = getchar(); 37 while (ch < '0' || ch > '9') ch = getchar(); 38 int x = 0; 39 while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); 40 return x; 41 } 42 43 int main() 44 { 45 int t; 46 t=read(); 47 int k=1; 48 while(t--){ 49 memset(c,0,sizeof(c)); 50 memset(d,0,sizeof(d)); 51 cout<<"Case #"<<k++<<": "<<endl; 52 n=read(),m=read(); 53 for(int i=1;i<=n;i++) { 54 a[i]=read(); 55 if(i&1) update(i/2+1,a[i],c); 56 else update(i/2,a[i],d); 57 } 58 while(m--){ 59 int z,x,y; 60 z=read(),x=read(),y=read(); 61 if(z==0){ 62 if(x&1) update(x/2+1,a[x]^y,c); 63 else update(x/2,a[x]^y,d); 64 a[x]=y; 65 } 66 else{ 67 if((y-x)&1) printf("0\n"); 68 else{ 69 int ans; 70 if(x&1) ans=sum(x/2,c)^sum(y/2+1,c); 71 else ans=sum(x/2-1,d)^sum(y/2,d); 72 printf("%d\n",ans); 73 } 74 } 75 } 76 } 77 return 0; 78 }
投递鹏芯微等公司10个岗位 >
查看12道真题和解析