自动搬运

查看原文

来自洛谷，原作者为

	VenusM1nT 醉后不知天在水 满船清梦压星河 | 明日方舟群 348956527

搬运于2025-08-24 22:04:54，当前版本为作者最后更新于2019-05-21 22:01:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

平衡树。

非常裸的平衡树，带翻转似乎只有平衡树能做了吧（

反正 $\texttt{fhq}$ 天下第一就是了【暴论】

依然是区间翻转打标记，区间查询就维护一个 $\texttt{sum}$ 数组，比较难搞的是这个区间异或，注意到题目中有写：$\texttt{d}\in[0,2^{20})$，考虑使用常用的套路，即将它拆成一位一位的分别维护，由于只有 $20$ 位，所以可以很轻松地存下来。

（尝试了一下新的毒瘤码风，各位感性理解一下吧qaq）

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define MAXN 100005
#define K 20
#define reg register
#define inl inline
#define int long long
using namespace std;
int n,m,a[MAXN];
struct FHQTreap
{
	int ch[MAXN][2],siz[MAXN],val[MAXN],key[MAXN],tag[MAXN],root,sze,num[MAXN][K+5],fg[MAXN],stk[MAXN],top;
	int sum[MAXN];
	bool rev[MAXN];
	inl void Mxr(reg int rt,reg int v)
	{
		tag[rt]^=v;
		val[rt]^=v;
		sum[rt]=0;
		for(reg int i=0;i<=K;i++) fg[i]=(v>>i)&1;
		for(reg int i=0;i<=K;i++)
		{
			if(fg[i]) num[rt][i]=siz[rt]-num[rt][i];
			sum[rt]+=(1<<i)*num[rt][i];
		}
	}
	inl void Psu(reg int rt)
	{
		siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1;
		sum[rt]=sum[ch[rt][0]]+sum[ch[rt][1]]+val[rt];
		for(reg int i=0;i<=K;i++) num[rt][i]=num[ch[rt][0]][i]+num[ch[rt][1]][i]+((val[rt]>>i)&1);
	}
	inl void Psd(reg int rt)
	{
		if(rev[rt])
		{
			swap(ch[rt][0],ch[rt][1]);
			if(ch[rt][0]) rev[ch[rt][0]]^=1;
			if(ch[rt][1]) rev[ch[rt][1]]^=1;
			rev[rt]=0;
		}
		if(tag[rt])
		{
			reg int v=tag[rt];
			tag[rt]=0;
			if(ch[rt][0]) Mxr(ch[rt][0],v);
			if(ch[rt][1]) Mxr(ch[rt][1],v);
		}
	}
	int Mrg(reg int x,reg int y)
	{
		if(!x || !y) return x+y;
		if(key[x]<key[y])
		{
			Psd(x);
			ch[x][1]=Mrg(ch[x][1],y);
			Psu(x);
			return x;
		}
		else
		{
			Psd(y);
			ch[y][0]=Mrg(x,ch[y][0]);
			Psu(y);
			return y;
		}
	}
	void Spt(reg int rt,reg int pos,reg int &x,reg int &y)
	{
		if(!rt) x=y=0;
		else
		{
			Psd(rt);
			if(pos<=siz[ch[rt][0]])
			{
				y=rt;
				Spt(ch[rt][0],pos,x,ch[rt][0]);
			}
			else
			{
				x=rt;
				Spt(ch[rt][1],pos-siz[ch[rt][0]]-1,ch[rt][1],y);
			}
			Psu(rt);
		}
	}
	inl int Nwd(reg int v)
	{
		reg int rt=++sze;
		siz[rt]=1;
		val[rt]=v;
		key[rt]=rand();
		tag[rt]=rev[rt]=0;
		ch[rt][0]=ch[rt][1]=0;
		return rt;
	}
	inl int Bld()
	{
		memset(stk,0,sizeof(stk));
		top=0;
		reg int x,pre;
		for(reg int i=1;i<=n;i++)
		{
			x=Nwd(a[i]);
			pre=0;
			while(top && key[stk[top]]>key[x])
			{
				Psu(stk[top]);
				pre=stk[top];
				stk[top--]=0;
			}
			if(top) ch[stk[top]][1]=x;
			ch[x][0]=pre;
			stk[++top]=x;
		}
		while(top) Psu(stk[top--]);
		return stk[1];
	}
	inl void Mdy(reg int l,reg int r,reg int v)
	{
		reg int x,y,z;
		Spt(root,r,x,z);
		Spt(x,l-1,x,y);
		Mxr(y,v);
		root=Mrg(Mrg(x,y),z);
	}
	inl void Rev(reg int l,reg int r)
	{
		reg int x,y,z;
		Spt(root,r,x,z);
		Spt(x,l-1,x,y);
		rev[y]^=1;
		root=Mrg(Mrg(x,y),z);
	}
	inl int Qry(reg int l,reg int r)
	{
		reg int x,y,z;
		Spt(root,r,x,z);
		Spt(x,l-1,x,y);
		reg int res=sum[y];
		root=Mrg(Mrg(x,y),z);
		return res;
	}
}T;
signed main()
{
	scanf("%lld %lld",&n,&m);
	for(reg int i=1;i<=n;i++) scanf("%lld",&a[i]);
	T.root=T.Bld();
	while(m--)
	{
		reg int opt,x,y,z;
		scanf("%lld %lld %lld",&opt,&x,&y);
		if(opt==1) T.Rev(x,y);
		else if(opt==2)
		{
			scanf("%lld",&z);
			T.Mdy(x,y,z);
		}
		else if(opt==3) printf("%lld\n",T.Qry(x,y));
	}
	return 0;
}