出题人题解 | #位运算？位运算！#

原题解链接：https://ac.nowcoder.com/discuss/149990

我们发现，这些位运算都是按位独立的,也就是说,我们可以将每一位分别维护, 而不是维护整个数字。

那我们可以先拆位，然后依次考虑如何实现这几个操作。

首先先看区间与，假设我们现在要与上$xx$,操作的区间是$[l,r][l,r]$,我们要考虑它对第$ww$位的影响。

那么很显然，如果$xx$的第$ww$位是$11$,那么这个操作对这一位没有影响。否则，就是将$[l,r][l,\; r]$的这一位赋值为$00$。

我们再来考虑区间或，假设我们现在要或上x,操作的区间是$[1,r][1,\; r]$,我们要考虑它对第$ww$位的影响。

那么很显然，如果$xx$的第$ww$位是$00$,那么这个操作对这一位没有影响。否则，就是将$[I,r][I,\; r]$的这一位赋值为$11$。

现在我们再来考虑区间循环左右移。

如果使用平衡树或来维护拆位后的序列，那么这个操作就相当于在不同位的平衡树上进行子树替换。

如果使用一颗线段树来维护拆位后的序列，那么这个操作就相当于将线段树节点上维护的信息进行循环平移。

使用单独的线段树维护每一位的序列也是进行子树替换。

区间求和的话直接求每一位的这一段有多少个$11$再乘上相应的$22$的幂次即可。

总复杂度:$O(nlo{g}^{2}n)O(n\; log^2\; n)$

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cassert>

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int MAXN=2E5+10;

int t[MAXN<<2][20],tg[MAXN<<2][20],sft[MAXN<<2];
int n,q,a[MAXN],Res[20];

void pushup(int x)
{
	for(int i=0;i<20;i++)
		t[x][i]=t[x<<1][i]+t[x<<1|1][i];
}

void apply_shift(int x,int b)
{
	b%=20;
	static int T1[20],T2[20];
	for(int i=0;i<20;i++)
		T1[(i+b+20)%20]=t[x][i],
		T2[(i+b+20)%20]=tg[x][i];
	for(int i=0;i<20;i++)
		t[x][i]=T1[i],tg[x][i]=T2[i];
}

void pushdown(int x,int l,int r)
{
	if(sft[x])
	{
		sft[x<<1]+=sft[x];sft[x<<1|1]+=sft[x];
		apply_shift(x<<1,sft[x]);apply_shift(x<<1|1,sft[x]);
		sft[x]=0;
	}
	int mid=(l+r)>>1;
	for(int i=0;i<20;i++)
	{
		if(tg[x][i]==0)
		{
			tg[x<<1][i]=tg[x<<1|1][i]=0;
			t[x<<1][i]=t[x<<1|1][i]=0;
			tg[x][i]=-1;
		}
		if(tg[x][i]==1)
		{
			tg[x<<1][i]=tg[x<<1|1][i]=1;
			t[x<<1][i]=mid-l+1;
			t[x<<1|1][i]=r-mid;
			tg[x][i]=-1;
		}
	}
}

void build(int x,int l,int r)
{
	if(l==r)
	{
		for(int i=0;i<20;i++)
			t[x][i]=(a[l]>>i)&1;
		return;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	pushup(x);
}

void And(int x,int l,int r,int cl,int cr,int v)
{
	if(cl<=l&&r<=cr)
	{
		for(int i=0;i<20;i++)
			if(!((v>>i)&1))
				t[x][i]=0,tg[x][i]=0;
		return;
	}
	int mid=(l+r)>>1;pushdown(x,l,r);
	if(cl<=mid) And(x<<1,l,mid,cl,cr,v);
	if(cr>mid)  And(x<<1|1,mid+1,r,cl,cr,v);
	pushup(x);
}

void Or(int x,int l,int r,int cl,int cr,int v)
{
	if(cl<=l&&r<=cr)
	{
		for(int i=0;i<20;i++)
			if((v>>i)&1)
				t[x][i]=r-l+1,tg[x][i]=1;
		return;
	}
	int mid=(l+r)>>1;pushdown(x,l,r);
	if(cl<=mid) Or(x<<1,l,mid,cl,cr,v);
	if(cr>mid)  Or(x<<1|1,mid+1,r,cl,cr,v);
	pushup(x);
}

void Shift(int x,int l,int r,int cl,int cr,int v)
{
	if(cl<=l&&r<=cr) return apply_shift(x,v),sft[x]+=v,void();
	int mid=(l+r)>>1;pushdown(x,l,r);
	if(cl<=mid) Shift(x<<1,l,mid,cl,cr,v);
	if(cr>mid)  Shift(x<<1|1,mid+1,r,cl,cr,v);
	pushup(x);
}

void query(int x,int l,int r,int ql,int qr)
{
	if(x==1) memset(Res,0,sizeof Res);
	if(ql<=l&&r<=qr)
	{
		for(int i=0;i<20;i++)
			Res[i]+=t[x][i];
		return;
	}
	int mid=(l+r)>>1;pushdown(x,l,r);
	if(ql<=mid) query(x<<1,l,mid,ql,qr);
	if(qr>mid)  query(x<<1|1,mid+1,r,ql,qr);
}

ll Query(int l,int r)
{
	ll Ret=0;
	query(1,1,n,l,r);
	for(int i=0;i<20;i++)	
		Ret+=(1ll<<i)*Res[i];
	return Ret;
}

int main()
{
	memset(tg,-1,sizeof tg);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1,l,r,v,opt;i<=q;i++)
	{
		scanf("%d%d%d%d",&opt,&l,&r,&v);
		if(opt==1) Shift(1,1,n,l,r,-v);
		if(opt==2) Shift(1,1,n,l,r,v);
		if(opt==3) Or(1,1,n,l,r,v);
		if(opt==4) And(1,1,n,l,r,v);
		if(opt==5) printf("%lld\n",Query(l,r));
	}
}