题目链接：https://nanti.jisuanke.com/t/40258
题意：给一个具有n个数字的序列，并且有要进行m个操作
操作有两种：
1.修改序列中一个数字的值
2.给定一个区间[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)=al^a(l+1)^...ar
分析：首先是要寻找规律,不难发现，当区间l到r之间的数有偶数个时，异或和恒为0，当为奇数个时，则与左端点奇偶性相同的数为本身，不同的也直接为0
我们考虑用线段树来进行维护，这里采用了建两个线段树的方法，学习学习。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; const int maxn=1e5+7; const ll inf=1e18+7; const double pi=acos(-1); struct node{ int l,r,v; }tree1[4*maxn],tree2[4*maxn]; int num[maxn],num1[maxn],num2[maxn]; int ans; void build1(int l,int r,int k){ tree1[k].l=l,tree1[k].r=r; if(l==r){ tree1[k].v=num1[l]; return ; } int m=(l+r)>>1; build1(l,m,k*2); build1(m+1,r,k*2+1); tree1[k].v=tree1[k*2].v^tree1[k*2+1].v; } void build2(int l,int r,int k){ tree2[k].l=l,tree2[k].r=r; if(l==r){ tree2[k].v=num2[l]; return ; } int m=(l+r)>>1; build2(l,m,k*2); build2(m+1,r,k*2+1); tree2[k].v=tree2[k*2].v^tree2[k*2+1].v; } void query1(int k,int x,int y){ if(tree1[k].l>=x&&tree1[k].r<=y){ ans^=tree1[k].v; //cout<<111<<endl; return ; } int m=(tree1[k].l+tree1[k].r)/2; if(x<=m) query1(k*2,x,y); if(y>m) query1(k*2+1,x,y); } void query2(int k,int x,int y){ if(tree2[k].l>=x&&tree2[k].r<=y){ ans^=tree2[k].v; //cout<<111<<endl; return ; } int m=(tree2[k].l+tree2[k].r)/2; if(x<=m) query2(k*2,x,y); if(y>m) query2(k*2+1,x,y); } void change1(int k,int x,int y){ if(tree1[k].l==tree1[k].r){ tree1[k].v=y;return; } int m=(tree1[k].l+tree1[k].r)/2; if(x<=m) change1(k*2,x,y); else change1(k*2+1,x,y); tree1[k].v=tree1[2*k].v^tree1[2*k+1].v; } void change2(int k,int x,int y){ if(tree2[k].l==tree2[k].r){ tree2[k].v=y;return; } int m=(tree2[k].l+tree2[k].r)/2; if(x<=m) change2(k*2,x,y); else change2(k*2+1,x,y); tree2[k].v=tree2[2*k].v^tree2[2*k+1].v; } int main(){ int T;cin>>T; for(int t=1;t<=T;t++){ int n,m;cin>>n>>m; for(int i=1;i<=n;i++)scanf("%d",&num[i]); int p=0; for(int i=1;i<=n;i+=2) num1[++p]=num[i]; p=0; for(int i=2;i<=n;i+=2) num2[++p]=num[i]; build1(1,(n+1)/2,1);build2(1,n/2,1); printf("Case #%d: ",t); for(int i=0;i<m;i++){ int opt,x,y;scanf("%d%d%d",&opt,&x,&y); if(opt==0){ if(x%2)change1(1,(x+1)/2,y); else change2(1,x/2,y); } if(opt==1){ if((y-x)%2){ printf("0 "); } else{ ans=0; if(x%2){ query1(1,(x+1)/2,(y+1)/2); } else query2(1,x/2,y/2); printf("%d ",ans); } } } } return 0; }
PS：实测发现线段树的一个结点用结构体会慢一些，可以直接建两个数组，左右端点可在函数里传进去
#include<iostream> #include<cstdio> using namespace std; const int maxn=1e5+10; int dat_j[4*maxn],dat_o[4*maxn]; int num1[maxn],num2[maxn],num[maxn]; void build1(int a,int l,int r){ if(l==r) dat_j[a]=num1[l]; else{ int mid=(l+r)>>1; build1(a<<1,l,mid); build1(a<<1|1,mid+1,r); dat_j[a]=dat_j[a<<1]^dat_j[a<<1|1]; } } void build2(int a,int l,int r){ if(l==r) dat_o[a]=num2[l]; else{ int mid=(l+r)>>1; build2(a<<1,l,mid); build2(a<<1|1,mid+1,r); dat_o[a]=dat_o[a<<1]^dat_o[a<<1|1]; } } void update1(int a,int l,int r,int m,int x){ if(l==r) dat_j[a]=x; else{ int mid=(l+r)>>1; if(m<=mid) update1(a<<1,l,mid,m,x); else update1(a<<1|1,mid+1,r,m,x); dat_j[a]=dat_j[a<<1]^dat_j[a<<1|1]; } } void update2(int a,int l,int r,int m,int x){ if(l==r) dat_o[a]=x; else{ int mid=(l+r)>>1; if(m<=mid) update2(a<<1,l,mid,m,x); else update2(a<<1|1,mid+1,r,m,x); dat_o[a]=dat_o[a<<1]^dat_o[a<<1|1]; } } int query1(int a,int l,int r,int x,int y){ if(x>r || y<l) return 0; if(x<=l && r<=y ) return dat_j[a]; int mid=(l+r)>>1; return query1(a<<1,l,mid,x,y)^query1(a<<1|1,mid+1,r,x,y); } int query2(int a,int l,int r,int x,int y){ if(x>r || y<l) return 0; if(x<=l && r<=y ) return dat_o[a]; int mid=(l+r)>>1; return query2(a<<1,l,mid,x,y)^query2(a<<1|1,mid+1,r,x,y); } int main(){ int T; scanf("%d",&T); for(int i=1;i<=T;i++){ printf("Case #%d: ",i); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&num[i]); int p=0; for(int i=1;i<=n;i+=2) num1[++p]=num[i]; p=0; for(int i=2;i<=n;i+=2) num2[++p]=num[i]; build1(1,1,(n+1)/2); build2(1,1,n/2); for(int i=0;i<m;i++){ int t,l,r; scanf("%d%d%d",&t,&l,&r); if(t==0){ if(l%2==1) update1(1,1,(n+1)/2,(l+1)/2,r); else update2(1,1,n/2,l/2,r); } else{ int res=0; int sum=r-l+1; if(sum%2==0) printf("0 "); else{ if(l%2==1){ printf("%d ",query1(1,1,(n+1)/2,(l+1)/2,(r+1)/2)); } else{ printf("%d ",query2(1,1,n/2,l/2,r/2)); } } } } } }