P4883 mzf的考验
题目背景
(mzf)立志要成为一个豪杰，当然，他也是一个(OIer)。 他希望自己除了会(OI)之外还会各种东西，比如心理学、吉他、把妹等等。 为了让自己有更大的魅力，他不驼背，不熬夜，整天锻炼，双目炯炯有神，是我们机房最不像(OIer)的人。 然而，在与我们格格不入若干天并且将《易经》研究透彻之后，承受不住我们对他另类的言论，他爆发了。 机房在那一刹那仿佛天塌地陷，世界末日。
题目描述
八卦有乾、坤、震、巽、坎、离、艮、兑； 两两组合，一上一下，形成了六十四卦，每卦六爻，一共三百八十四爻。 爻分阴阳，阳爻性属阳刚，阴爻性属阴柔。天下之大，无奇不有。千奇百怪，皆出此处。 (mzf)研究透彻了易经之后，画出了(n)个奇怪的图案。他说那是他改进出来的更强大的卜卦体系。 每一个图案有二十行，每一行要么是阴爻((0))，要么是阳爻((1))，作为一个(OIer)，我们可以将卦象看成一个个二进制串； 他将(n)个图案画在了符纸上，然后进行(m)次操作：
操作1：翻转区间([l,r])的图案，比如((3,1,2,5))变成((5,2,1,3))；
操作2：(mzf)画地为卦，将([l,r])之间的卦象都异或上新画的那个卦象；
操作3：(mzf)会询问机房里的其他人([l,r])之间卦象代表的二进制数权值和。
如果不能正确回答每个操作(3)，那么机房风水格局将会改变，我们都将...！
由于(mzf)疯狂之下将我们都捆♂绑♂了起来，所以只能求求你来帮我们解决这个问题。
输入输出格式
输入格式：
第一行两个正整数：(n)，(m)（(n)为序列长度，(m)为操作个数）
第二行(n)个正整数：(a[i]) (用(10)进制数表示每个卦象)((1<=i<=n))
接下来(m)行：每行首先一个正整数(opt)表示操作类型
(opt==1)：两个正整数：(l)，(r)。请翻转区间([l,r])；
(opt==2)：三个正整数：(l)，(r)，(d)。请将区间([l,r])中的所有卦象都异或卦象(d)。((0<=d<=10^5))
(opt==3)：两个正整数：(l)，(r)。请查询区间([l,r])的卦象权值和。
输出格式：
对于每个 (opt==3) 的情况，输出一行答案。
说明
对于(20\%)的数据，(n<=1000)，(m<=1000)
对于另外(20\%)的数据，不存在操作(1)
对于另外(20\%)的数据，保证(n)为(2)的次幂，且在操作(1)中，保证(l=i imes(2^j)+1,r=(i+1) imes(2^j))，其中(i)，(j)为任意值
对于(100\%)的数据，(n<=10^5)，(m<=5 imes 10^4)，(1<=l<=r<=n)，(0<=d<2^{20})
发现，区间翻转要用平衡树，区间异或要用线段树打标记
平衡树不能打标记的原因是不能快速更新子树答案
我们可以把每一位拆开，然后对每一位维护区间1的个数，就可以快速更新子树答案啦
复杂度：(O(mlogdlogn))
Code:
#include <cstdio>
#include <cstdlib>
#define ls ch[now][0]
#define rs ch[now][1]
#define ll long long
const int N=1e5+10;
int ch[N][2],dxor[N],siz[N],val[N],tag[N],tmp,root;
int n,m,a[N];
ll sum[N][21],dat[N][21],pow[21];
void Reverse(int now){tag[now]^=1,tmp=ls,ls=rs,rs=tmp;}
void updata(int now)
{
for(int i=0;i<=20;i++)
sum[now][i]=sum[ls][i]+sum[rs][i]+dat[now][i];
siz[now]=siz[ls]+siz[rs]+1;
}
void eor(int now,int x)
{
for(int i=0;i<=20;i++)
if(x>>i&1)
{
sum[now][i]=1ll*siz[now]-sum[now][i];
dat[now][i]^=1;
}
dxor[now]^=x;
}
void pushdown(int now)
{
if(tag[now])
{
if(ls) Reverse(ls);
if(rs) Reverse(rs);
tag[now]^=1;
}
if(dxor[now])
{
if(ls) eor(ls,dxor[now]);
if(rs) eor(rs,dxor[now]);
dxor[now]=0;
}
}
void split(int now,int k,int &x,int &y)
{
if(!now) {x=y=0;return;}
pushdown(now);
if(siz[ls]+1<=k)
x=now,split(rs,k-siz[ls]-1,rs,y);
else
y=now,split(ls,k,x,ls);
updata(now);
}
int Merge(int x,int y)
{
if(!x||!y) return x|y;
pushdown(x),pushdown(y);
if(val[x]<val[y])
{
ch[x][1]=Merge(ch[x][1],y);
updata(x);
return x;
}
else
{
ch[y][0]=Merge(x,ch[y][0]);
updata(y);
return y;
}
}
void reverse(int l,int r)
{
int x,y,z;
split(root,r,x,y);
split(x,l-1,x,z);
Reverse(z);
root=Merge(x,Merge(z,y));
}
void segdxor(int l,int r,int xo)
{
int x,y,z;
split(root,r,x,y);
split(x,l-1,x,z);
eor(z,xo);
root=Merge(x,Merge(z,y));
}
ll query(int l,int r)
{
int x,y,z;ll s=0;
split(root,r,x,y);
split(x,l-1,x,z);
for(int i=0;i<=20;i++)
s+=sum[z][i]*pow[i];
root=Merge(x,Merge(z,y));
return s;
}
int build(int l,int r,int pre)
{
if(l>r) return 0;
if(l==r)
{
val[l]=pre+rand();
for(int i=0;i<=20;i++)
sum[l][i]=dat[l][i]=1ll*(a[l]>>i&1);
siz[l]=1;
return l;
}
int now=rand()%(r+1-l)+l;
val[now]=pre+rand();
for(int i=0;i<=20;i++)
dat[now][i]=1ll*(a[now]>>i&1);
ls=build(l,now-1,val[now]);
rs=build(now+1,r,val[now]);
updata(now);
return now;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=0;i<=20;i++) pow[i]=1ll<<i;
root=build(1,n,0);
for(int op,l,r,d,i=1;i<=m;i++)
{
scanf("%d%d%d",&op,&l,&r);
if(op==1) reverse(l,r);
else if(op==2)
{
scanf("%d",&d);
segdxor(l,r,d);
}
else
printf("%lld
",query(l,r));
}
return 0;
}
2018.9.9