题意：给出N个数，M个操作。操作有修改和询问两种，每次修改将一个数改成另一个数，每次询问一个区间的所有连续子区间的异或和。n,m<=100000,ai<=1000
题解：
当年（其实也就是今年）做不出来的题。。D1T1啊。。。
因为ai<=1000，我们可以拆位处理。拆成10个二进制位，每位开1棵线段树。
对于每个节点，维护：
d：这段区间的异或和
L[0]，L[1]：子区间一定从左端点开始，异或和为0，1的子区间分别有多少个
R[0]，R[1]：子区间一定从右端点开始，异或和为0，1的子区间分别有多少个
s[0]，s[1]:异或和为0，1的子区间分别有多少个
然后重点就是合并啦。
node upd(int ind,int tmp,node lc,node rc)
{
int dl=lc.d,dr=rc.d;
node x;
if(tmp!=) x=t[ind][tmp];
x.d=lc.d^rc.d;
x.L[]=(lc.L[]+rc.L[(dl==) ? :])%mod;
x.L[]=(lc.L[]+rc.L[(dl==) ? :])%mod;
x.R[]=(rc.R[]+lc.R[(dr==) ? :])%mod;
x.R[]=(rc.R[]+lc.R[(dr==) ? :])%mod;
x.s[]=(lc.s[]+rc.s[]+(lc.R[]*rc.L[])%mod+(lc.R[]*rc.L[])%mod)%mod;
x.s[]=(lc.s[]+rc.s[]+(lc.R[]*rc.L[])%mod+(lc.R[]*rc.L[])%mod)%mod;
return x;
}
我打成node形式。。因为最后查询的时候有多个区间也要合并。。
代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std; typedef long long LL;
const int N=;
const LL mod=;
struct node{
int l,r,lc,rc,d;
LL L[],R[],s[];
//L:从左开始
//R:从右开始
//s:总答案
}t[][*N];
char c[];
int n,m,tl,a[N][];
LL bit[]; node upd(int ind,int tmp,node lc,node rc)
{
int dl=lc.d,dr=rc.d;
node x;
if(tmp!=) x=t[ind][tmp];
x.d=lc.d^rc.d;
x.L[]=(lc.L[]+rc.L[(dl==) ? :])%mod;
x.L[]=(lc.L[]+rc.L[(dl==) ? :])%mod;
x.R[]=(rc.R[]+lc.R[(dr==) ? :])%mod;
x.R[]=(rc.R[]+lc.R[(dr==) ? :])%mod;
x.s[]=(lc.s[]+rc.s[]+(lc.R[]*rc.L[])%mod+(lc.R[]*rc.L[])%mod)%mod;
x.s[]=(lc.s[]+rc.s[]+(lc.R[]*rc.L[])%mod+(lc.R[]*rc.L[])%mod)%mod;
return x;
} int bt(int ind,int l,int r)
{
int x=++tl;
t[ind][x].l=l;t[ind][x].r=r;
t[ind][x].lc=t[ind][x].rc=;
t[ind][x].d=;
memset(t[ind][x].L,,sizeof(t[ind][x].L));
memset(t[ind][x].R,,sizeof(t[ind][x].R));
memset(t[ind][x].s,,sizeof(t[ind][x].s));
if(l<r)
{
int mid=(l+r)/;
t[ind][x].lc=bt(ind,l,mid);
t[ind][x].rc=bt(ind,mid+,r);
int lc=t[ind][x].lc,rc=t[ind][x].rc;
t[ind][x]=upd(ind,x,t[ind][lc],t[ind][rc]);
}
else
{
int d=a[l][ind];
t[ind][x].d=d;
t[ind][x].L[d]=t[ind][x].R[d]=t[ind][x].s[d]=;
}
return x;
} void change(int ind,int x,int p,int d)
{
if(t[ind][x].l==t[ind][x].r)
{
t[ind][x].d=d;
t[ind][x].L[d]=t[ind][x].R[d]=t[ind][x].s[d]=;
t[ind][x].L[d^]=t[ind][x].R[d^]=t[ind][x].s[d^]=;
return ;
}
int lc=t[ind][x].lc,rc=t[ind][x].rc,mid=(t[ind][x].l+t[ind][x].r)/;
if(p<=mid) change(ind,lc,p,d);
else change(ind,rc,p,d);
t[ind][x]=upd(ind,x,t[ind][lc],t[ind][rc]);
} node query(int ind,int x,int l,int r)
{
if(t[ind][x].l==l && t[ind][x].r==r) return t[ind][x];
int lc=t[ind][x].lc,rc=t[ind][x].rc,mid=(t[ind][x].l+t[ind][x].r)/;
if(r<=mid) return query(ind,lc,l,r);
else if(l>mid) return query(ind,rc,l,r);
else
{
node a0=query(ind,lc,l,mid);
node a1=query(ind,rc,mid+,r);
return upd(,,a0,a1);
}
} void output(int ind,int x)
{
int lc=t[ind][x].lc,rc=t[ind][x].rc;
printf("l=%d r=%d d=%d l0=%lld l1=%lld r0=%lld r1=%lld s0=%lld s1=%lld\n",t[ind][x].l,t[ind][x].r,t[ind][x].d,t[ind][x].L[],t[ind][x].L[],t[ind][x].R[],t[ind][x].R[],t[ind][x].s[],t[ind][x].s[]);
if(lc) output(ind,lc);
if(rc) output(ind,rc);
} int main()
{
freopen("a.in","r",stdin);
freopen("me.out","w",stdout);
// freopen("cardcaptor.in","r",stdin);
// freopen("cardcaptor.out","w",stdout);
scanf("%d",&n);
int x,ind;node now;
bit[]=;
for(int i=;i<=;i++) bit[i]=bit[i-]*;
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
{
scanf("%d",&x);
ind=;
while(x)
{
a[i][ind]=x%;
x/=;
ind++;
}
}
scanf("%d",&m);
for(int i=;i<;i++) {tl=;bt(i,,n);}
for(int i=;i<=m;i++)
{
scanf("%s",c);
if(c[]=='Q')
{
int l,r;LL ans=;
scanf("%d%d",&l,&r);
for(int j=;j<;j++)
{
now=query(j,,l,r);
ans=(ans+(bit[j]*now.s[])%mod)%mod;
}
printf("%lld\n",ans);
}
else
{
int ind=,p,d;
scanf("%d%d",&p,&d);
while(d)
{
change(ind,,p,d%);
d/=;
ind++;
}
for(int j=ind;j<;j++) change(j,,p,);
}
}
return ;
}