链接: https://atcoder.jp/contests/abc185/tasks/abc185_f
题意: 给你n和m,n表示数组长度,m表示操作数量,然后给出数组,再给出m行操作,每行输入t,x,y。若t为1,则需将Ai的值改为Ai^y。t为2,则输出 [ l , r ] [l,r] [l,r]区间的异或值。
思路:该题需要单点修改和区间查询,很明显可以使用线段树进行操作,我首先用的是线段树,但是后面看其他大佬的题解有更为简单的方式,也就是树状数组,因为树状数组可以进行单点修改,且异或值可以通过树状数组维护为一个前缀和,查询 [ l , r ] [l,r] [l,r]区间时,只需查询 [ 1 , l − 1 ] [1,l-1] [1,l−1]的异或值和 [ 1 , r ] [1,r] [1,r]的异或值然后对两个值进行异或输出即可。
树状数组代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll tr[300010];
ll a[300010];
int n,m;
int lowbit(int x){
return x&(-x);
}
void add(int x,ll val){
while(x<=300005){
tr[x]=tr[x]^val;
x+=lowbit(x);
}
}
ll sum(int x){
ll ans=0;
while(x){
ans=ans^tr[x];
x-=lowbit(x);
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
ll w;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
add(i,a[i]);
}
int t,x,y;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&t,&x,&y);
if(t==1){
add(x,y);
}
else{
ll ans1=sum(y);
ll ans2=sum(x-1);
printf("%lld\n",ans2^ans1);
}
}
return 0;
}
线段树代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=300010;
ll p[maxn];
int n,m;
struct tt{
int l,r;
ll val;
};
tt tr[maxn<<2];
void build(int l,int r,int idx){
tr[idx].l=l,tr[idx].r=r;
if(l==r){
tr[idx].val=p[l];
return;
}
else{
int mid=(l+r)>>1;
build(l,mid,(idx<<1)|1);
build(mid+1,r,(idx<<1)+2);
tr[idx].val=tr[(idx<<1)|1].val^tr[(idx<<1)+2].val;
}
}
ll query(int l,int r,int pos){
if(r<l)return 0;
if(tr[pos].l>=l&&tr[pos].r<=r){
return tr[pos].val;
}
else{
int mid=(tr[pos].l+tr[pos].r)>>1;
if(r<=mid)return query(l,r,(pos<<1)|1);
else if(l>mid)return query(l,r,(pos<<1)+2);
else{
ll ans1=query(l,r,(pos<<1)|1);
ll ans2=query(l,r,(pos<<1)+2);
return ans1^ans2;
}
}
}
void updata(int pos,ll x,int idx){
if(tr[idx].l==tr[idx].r){
tr[idx].val=tr[idx].val^x;
return;
}
else{
int mid=(tr[idx].l+tr[idx].r)>>1;
if(pos<=mid)updata(pos,x,(idx<<1)|1);
else updata(pos,x,(idx<<1)+2);
tr[idx].val=tr[(idx<<1)|1].val^tr[(idx<<1)+2].val;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&p[i]);
}
build(1,n,0);
int t,x,y;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&t,&x,&y);
if(t==1){
updata(x,y,0);
}
else{
ll ans1=query(1,x-1,0);
ll ans2=query(1,y,0);
printf("%lld\n",ans1^ans2);
}
}
return 0;
}