> ### Description
>
> 给定一个长为$n(n<=10^5)$的数组
>
> 数组里的数不超过$10^6$
>
> 有两种操作：
>
> 1:求$sum[l,r]$;
>
> 2:对$[l,r]$中的所有数和$x$异或
>
> ### Input
>
> 第一行一个整数$n$,代表有一个长度为$n$的数组。
>
> 第二行$n$个整数,代表$a_i$
>
> 第三行为一个整数$m$,代表有$m$次操作。
>
> 接下来$m$行每行描述一个操作。
>
> ### Output
>
> 对于每一个操作$1$,输出一行代表$sum[l,r]$.
这题不错,**线段树+二进制拆位**
由于异或不具有叠加性,所以不能用$lazy$标记直接异或。
我们记录$tr[o][i]$代表当前节点$o$,二进制位$i$上是$1$的数有多少个。
由于,如果某一二进制位上原来为$1$,且当前异或的数$x$,当前二进制位上也有$1$,那么我们的当前$tr[o][i]=r-l+1-tr[o][i]$。
可以理解为$01$交换。
然后由于$2^{20}$比$10^6$要大。
所以只需要拆到$20$即可。
然后直接计算即可。
PS：记得开$long \ long$！
``代码``
```c++
#include<cstdio>
#include<algorithm>
#include<iostream>
#define int long long
#define R register
using namespace std;
const int gz=1e5+8;
inline void in(R int &x)
{
R int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,tr[gz<<2][21],tg[gz<<2],m;
#define ls o<<1
#define rs o<<1|1
inline void up(R int o)
{
for(R int i=20;~i;i--)
tr[o][i]=tr[ls][i]+tr[rs][i];
}
void build(R int o,R int l,R int r)
{
if(l==r)
{
R int x;in(x);
for(R int i=20;~i;i--)
if((x>>i)&1)tr[o][i]++;
return;
}
R int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(o);
}
inline void down(R int o,R int l,R int r)
{
if(tg[o]==0)return;
tg[ls]^=tg[o];tg[rs]^=tg[o];
R int mid=(l+r)>>1;
for(R int i=20;~i;i--)
{
if((tg[o]>>i)&1)
tr[ls][i]=mid-l+1-tr[ls][i],
tr[rs][i]=r-mid-tr[rs][i];
}
tg[o]=0;
return;
}
void change(R int o,R int l,R int r,R int x,R int y,R int k)
{
if(x<=l and y>=r)
{
tg[o]^=k;
for(R int i=20;~i;i--)
if((k>>i)&1)
tr[o][i]=r-l+1-tr[o][i];
return;
}
down(o,l,r);
int mid=(l+r)>>1;
if(x<=mid)change(ls,l,mid,x,y,k);
if(y>mid) change(rs,mid+1,r,x,y,k);
up(o);
}
int query(R int o,R int l,R int r,R int x,R int y)
{
if(x<=l and y>=r)
{
R int res=0;
for(R int i=20;~i;i--)
res+=(1<<i)*tr[o][i];
return res;
}
down(o,l,r);
R int mid=(l+r)>>1,as=0;
if(x<=mid)as+=query(ls,l,mid,x,y);
if(y>mid)as+=query(rs,mid+1,r,x,y);
return as;
}
signed main()
{
in(n);build(1,1,n);in(m);
for(R int opt,l,r,x;m;m--)
{
in(opt);
if(opt==1)
{
in(l),in(r);
printf("%lld\n",query(1,1,n,l,r));
}
else
{
in(l),in(r),in(x);
change(1,1,n,l,r,x);
}
}
}
```