题解：P5586 [P5350] 序列 (加强版)
题意
维护一个序列，支持区间求和，区间赋值，区间加，区间复制和交换，区间翻转，强制在线且数据不一定随机。
思路
感觉用什么都可以做的样子
我们将目光指向了最后一个操作：区间翻转。
这题是平衡树是跑不了了。
然后因为还需要区间复制和交换，所以就需要可持久化。
赋值，区间加，区间翻转分别记一个
在每次
注意到出题人说不卡空间，那多半是卡空间。所以需要通过定期的重构保证节点个数不爆炸。
对了，随机的优先级占用空间，不如什么时候用就什么时候随机，不费空间。
Code
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]<<' ';
}