题解：P5586 [P5350] 序列 (加强版)

const int N=4e6+5;
const int mod=1e9+7;
int n,m,a[300005];

#define Tree(u) tree[u]
#define SUM(u) tree[u].SUM
#define Plus(u) tree[u].Plus//区间加Tag
#define Cov(u) tree[u].Cov//区间赋值Tag
#define Rev(u) tree[u].Rev//区间翻转Tag
#define lson(u) tree[u].son[0]
#define rson(u) tree[u].son[1]
#define son(u,i) tree[u].son[i]
#define SIZE(u) tree[u].SIZE
#define Val(u) tree[u].Val
#define mid (left+right>>1)
struct Node
{
	int SUM,Plus,Cov,son[2],SIZE,Val; bool Rev;
	Node(int sum=0,int pls=0,int ch=0,int rev=0,int son0=0,int son1=0,int Size=0,int val=0)
	{
		SUM=sum,Plus=pls,Cov=ch,Rev=rev,son[0]=son0,son[1]=son1,SIZE=Size,Val=val;
	}
};
struct FHQ_treap
{
	Node tree[N]; int root,tot;
	void Clone(int &u)
	{
		Tree(++tot)=Tree(u);
		u=tot;
	}
	int New_Node(int val)
	{
		Tree(++tot)=Node(val,0,-1,0,0,0,1,val);
		return tot;
	}
	void pushup(int u)
	{
		SIZE(u)=SIZE(lson(u))+SIZE(rson(u))+1;
		SUM(u)=(1ll*SUM(lson(u))+SUM(rson(u))+Val(u))%mod;
	}
	void Push_Rev(int u)
	{
		if(!u) return ;
		Rev(u)^=1;
		swap(lson(u),rson(u));
	}
	void Push_Cov(int u,int x)
	{
		if(!u) return ;
		Val(u)=x;
		Plus(u)=0;
		Cov(u)=x;
		SUM(u)=1ll*x*SIZE(u)%mod;
	}
	void Push_Plus(int u,int x)
	{
		if(!u) return ;
		(Val(u)+=x)%=mod;
		(Plus(u)+=x)%=mod;
		SUM(u)=(1ll*x*SIZE(u)+SUM(u))%mod;
	}
	void pushdown(int u)
	{
		if(!Plus(u) && Cov(u)==-1 && !Rev(u)) return ;
		if(lson(u)) Clone(lson(u));
		if(rson(u)) Clone(rson(u));
		if(Rev(u))
		{
			Push_Rev(lson(u));
			Push_Rev(rson(u));
			Rev(u)=0;
		}
		if(Cov(u)!=-1)
		{
			Push_Cov(lson(u),Cov(u));
			Push_Cov(rson(u),Cov(u));
			Cov(u)=-1;
		}
		if(Plus(u))
		{
			Push_Plus(lson(u),Plus(u));
			Push_Plus(rson(u),Plus(u));
			Plus(u)=0;
		}
	}
	int Merge(int u,int v)
	{
		if(!u || !v) return u+v;
		if(rand()%(SIZE(u)+SIZE(v))<SIZE(u))//实时随机
		{
			Clone(u); pushdown(u);
			rson(u)=Merge(rson(u),v);
			pushup(u); return u;
		}
		else
		{
			Clone(v); pushdown(v);
			lson(v)=Merge(u,lson(v));
			pushup(v); return v;
		}
	}
	void Split(int u,int k,int &x,int &y)
	{
		if(!u){x=y=0;return ;}
		if(SIZE(lson(u))<k)
		{
			x=u;Clone(x);pushdown(x);
			Split(rson(x),k-SIZE(lson(x))-1,rson(x),y);
			pushup(x);
		}
		else
		{
			y=u;Clone(y);pushdown(y);
			Split(lson(y),k,x,lson(y));
			pushup(y);
		}
	}
	int Qsum(int L,int R)
	{
		int A,B,C;
		Split(root,R,B,C);
		Split(B,L-1,A,B);
		int Answer=SUM(B);
		root=Merge(A,Merge(B,C));
		return Answer;
	}
	void update(int L,int R,int k)
	{
		int A,B,C;
		Split(root,R,B,C);
		Split(B,L-1,A,B);
		Clone(B);
		Push_Cov(B,k);
		root=Merge(A,Merge(B,C));
	}
	void ADD(int L,int R,int k)
	{
		int A,B,C;
		Split(root,R,B,C);
		Split(B,L-1,A,B);
		Clone(B);
		Push_Plus(B,k);
		root=Merge(A,Merge(B,C));
	}
	void Reverse(int L,int R)
	{
		int A,B,C;
		Split(root,R,B,C); 
		Split(B,L-1,A,B);
		Clone(B);
		Push_Rev(B);
		root=Merge(A,Merge(B,C)); 
	}
	void Copy(int L1,int R1,int L2,int R2)
	{
		int A,B,C,D,E,Flag=1;
		if(R1>R2)
		{
			swap(L1,L2);
			swap(R1,R2);
			Flag=0;
		}
		Split(root,R2,D,E);
		Split(D,L2-1,C,D);
		Split(C,R1,B,C);
		Split(B,L1-1,A,B);
		if(Flag) root=Merge(A,Merge(B,Merge(C,Merge(B,E))));
		else root=Merge(A,Merge(D,Merge(C,Merge(D,E))));
	}
	void Swap(int L1,int R1,int L2,int R2)
	{
		int A,B,C,D,E;
		if(R1>R2)
		{
			swap(L1,L2);
			swap(R1,R2);
		}
		Split(root,R2,D,E);
		Split(D,L2-1,C,D);
		Split(C,R1,B,C);
		Split(B,L1-1,A,B);
		root=Merge(A,Merge(D,Merge(C,Merge(B,E))));
	}
	int build(int left=1,int right=n)
	{
		if(left>right) return 0;
		int u=New_Node(a[mid]);
		lson(u)=build(left,mid-1);
		rson(u)=build(mid+1,right);
		pushup(u); return u;
	}
	void dfs(int u)
	{
		if(!u) return ;
		pushdown(u);
		dfs(lson(u));
		a[++n]=Val(u);
		dfs(rson(u));
	}
	void init(){root=tot=0;root=build();}
}Treap;

void __huanghongjun__Shen()
{
	int i,kind,L,R,k,LL,RR,last_ans=0;
	cin>>n>>m;
	for(i=1;i<=n;i++) cin>>a[i];
	Treap.init();
	while(m--)
	{
		cin>>kind>>L>>R; L^=last_ans,R^=last_ans;
		if(kind==1) cout<<(last_ans=Treap.Qsum(L,R))<<'\n';
		if(kind==2){cin>>k;k^=last_ans;Treap.update(L,R,k);}
		if(kind==3){cin>>k;k^=last_ans;Treap.ADD(L,R,k);}
		if(kind==4){cin>>LL>>RR;LL^=last_ans;RR^=last_ans;Treap.Copy(L,R,LL,RR);}
		if(kind==5){cin>>LL>>RR;LL^=last_ans;RR^=last_ans;Treap.Swap(L,R,LL,RR);}
		if(kind==6) Treap.Reverse(L,R); 
		if(Treap.tot>=3e6)
		{
			n=0;
			Treap.dfs(Treap.root);
			Treap.init();
		}
	}
	n=0; Treap.dfs(Treap.root);
	for(i=1;i<=n;i++) cout<<a[i]<<' ';
}