题意：
给定一个序列，给定两种操作：
-
将一个区间异或上一个给定的值。
-
给定 \(l,r\) 求
\(0\le a_i,x< 2^{30}\)，\(1\le l\le r\le n\)
思路
-
由于操作数以及区间过大，一位一位地去模拟肯定是不行的。因此考虑去离线下来拆位，对于每一个操作的每一位单独维护贡献。
-
由于是前缀或，因此对于每一位而言，只要有一个数在这一位上是1，那后面的所有值也一定都是1。
因此问题就转化成了维护区间第一个1所在的位置，答案就是这个位置与右端点的距离。 -
考虑如何去维护这个东西。显然去查找不可能直接找，需要去二分。但同时还要维护操作1，因此考虑用线段树去维护。
那怎么在线段树上查找呢？考虑维护节点所代表的区间是不是全为零，如果全为零的话就向右儿子搜，否则向左儿子搜。
但由于异或操作，还可以维护一个是否全是1方便修改。需要修改的时候将两个标记交换就可以了。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int p=1073741824;
const int N=2e5+7;
int n,m,a[N],loc;bool s1[N<<2],s2[N<<2],b[N],sign,tag[N<<2];
struct ques
{
int opt,l,r,x;long long ans=0;
}q[N];
#define ls (u<<1)
#define rs ((u<<1)|1)
void push_up(int u)
{
s1[u]=s1[ls]|s1[rs];s2[u]=s2[ls]|s2[rs];
}
void push_down(int u)
{
if(!tag[u]) return;
swap(s1[ls],s2[ls]),swap(s1[rs],s2[rs]);
tag[ls]^=1,tag[rs]^=1;
tag[u]=0;
}
void build(int u,int l,int r)
{
tag[u]=0;if(l==r){s1[u]=b[l],s2[u]=b[l]^1;return;}
int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);
push_up(u);
}
void modify(int u,int l,int r,int ql,int qr)
{
if(l>=ql&&r<=qr) {swap(s1[u],s2[u]),tag[u]^=1;return;}
int mid=(l+r)>>1;push_down(u);
if(mid>=ql) modify(ls,l,mid,ql,qr);if(mid<qr) modify(rs,mid+1,r,ql,qr);
push_up(u);
}
void query(int u,int l,int r,int ql,int qr)
{
if((!s1[u])||sign||r<ql||l>qr) return;
if(l==r) {if(s1[u]&&l<loc&&l>=ql)loc=l,sign=1;return;}
int mid=(l+r)>>1;push_down(u);
if(mid>=ql) query(ls,l,mid,ql,qr);
if(sign) return;
if(mid<qr) query(rs,mid+1,r,ql,qr);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) {cin>>q[i].opt>>q[i].l>>q[i].r;if(q[i].opt==1) cin>>q[i].x;}
for(int k=0;k<=30;k++)
{
for(int i=1;i<=n;i++) b[i]=(a[i]>>k)&1;build(1,1,n);
for(int i=1;i<=m;i++)
{
if(q[i].opt==1) {if(((q[i].x>>k)&1)==1) modify(1,1,n,q[i].l,q[i].r);}
else
{
sign=0;loc=q[i].r+1;query(1,1,n,q[i].l,q[i].r);
q[i].ans=(q[i].ans+1ll*(q[i].r-loc+1ll)*(1ll<<k)%p)%p;
}
}
}
for(int i=1;i<=m;i++) if(q[i].opt==2) cout<<q[i].ans<<'\n';
return 0;
}