首先看到询问有关位运算考虑拆为处理，由于 \(a_i \leq 10^3\) 所以一个数最多有 \(10\) 位。
我们考虑对于一位它的贡献是多少，我们发现第 \(j\) 位一个连续段的异或值为 \(1\) 时会产生 \(2^j\) 的贡献，所以问题转化为快速求所有位上异或和为 \(1\) 的区间个数。
我们可以使用线段树维护，对于每一位开一个线段树，值域为 \(1\) 到 \(n\)，内部记录当前区间内异或前缀和为 \(0\) 的个数 \(s0\)，容易知道区间内异或前缀和为 \(1\) 的个数 \(s1\) 为区间长度减去维护值。同时也容易根据异或性质推出区间异或值为 \(1\) 的区间个数为 \(s0 \cdot s1\)。
修改时同样按位处理，若一位为 \(1\) 则将它后面的前缀跟着更新。
剩下的就是基本的线段树区间修改区间查询了。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define ll long long
#define debug cout<<"DEBUG"<<endl;
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define imp map<int,int>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
const int N=1e5+5,mod=1e8+7;
int n,m,a[N],s[N];
struct SEG{
int seg[N<<2],lz[N<<2];
void build(int p,int l,int r){
lz[p]=0;
if(l==r){
seg[p]=s[l];
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
seg[p]=seg[ls(p)]+seg[rs(p)];
}
void pushdown(int p,int l,int r){
if(!lz[p]) return;
int mid=(l+r)>>1;
seg[ls(p)]=mid-l+1-seg[ls(p)];
seg[rs(p)]=r-mid-seg[rs(p)];
lz[ls(p)]^=1;
lz[rs(p)]^=1;
lz[p]=0;
}
void change(int p,int nx,int ny,int l,int r){
if(l<=nx&&ny<=r){
lz[p]^=1;
seg[p]=ny-nx+1-seg[p];
return;
}
pushdown(p,nx,ny);
int mid=(nx+ny)>>1;
if(l<=mid) change(ls(p),nx,mid,l,r);
if(mid<r) change(rs(p),mid+1,ny,l,r);
seg[p]=seg[ls(p)]+seg[rs(p)];
}
int query(int p,int nx,int ny,int l,int r){
if(l<=nx&&ny<=r){
return seg[p];
}
pushdown(p,nx,ny);
int mid=(nx+ny)>>1;
int sum=0;
if(l<=mid) sum+=query(ls(p),nx,mid,l,r);
if(mid<r) sum+=query(rs(p),mid+1,ny,l,r);
return sum;
}
}rt[10];
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<10;i++){
for(int j=1;j<=n;j++){
s[j]=s[j-1]^((a[j]>>i)&1);
// printf("%d ",s[j]);
}
rt[i].build(1,1,n);
}
scanf("%d",&m);
while(m--){
char c;
int x,y;
scanf(" %c%d%d",&c,&x,&y);
// printf("%lld %lld\n",x,y);
if(c=='Q'){
ll ans=0;
for(int i=0;i<10;i++){
ll now=rt[i].query(1,1,n,x-1,y);
now=(ll)now*(y-x+2-now)%mod*(1<<i)%mod;
ans+=now;
}
printf("%lld\n",ans%mod);
}else{
for(int i=0;i<10;i++){
if(((a[x]>>i)&1)!=((y>>i)&1)) rt[i].change(1,1,n,x,n);
}
a[x]=y;
}
}
return 0;
}