Code:
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MaxN=3e5+5,MaxM=4e6+5,mod=1e9+7;
inline int Add(int x,int y){
if(x+y>=mod)return x+y-mod;
return x+y;
}
inline void ADD(int&x,int y){
x=Add(x,y);
}
struct Balance_Tree{
int l,r,fval,size,rev,val,sum,addtag,tag;
inline void print(){
cerr<<l<<" "<<r<<" "<<fval<<" "<<size<<" "<<rev<<" "<<val<<" "<<sum<<" "<<addtag<<" "<<tag<<endl;
}
}tr[MaxM];
int num,a[MaxN];
struct FHQ{
int rt;
FHQ(){rt=0;}
inline void rever(int p){
swap(tr[p].l,tr[p].r);
tr[p].rev^=1;
}
inline void add(int p,int k){
ADD(tr[p].val,k);
ADD(tr[p].addtag,k);
ADD(tr[p].sum,1ll*k*tr[p].size%mod);
}
inline void update(int p,int k){
tr[p].val=tr[p].tag=k;
tr[p].addtag=0;
tr[p].sum=1ll*k*tr[p].size%mod;
}
inline void pushup(int p){
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;
tr[p].sum=Add(tr[tr[p].l].sum,Add(tr[tr[p].r].sum,tr[p].val));
}
inline int INSERT(int x){
tr[++num]={0,0,rand(),1,0,x,x,0,-1};
return num;
}
inline int cpy(int x){
int p=INSERT(0);
tr[p]=tr[x];
return p;
}
inline void pushdown(int p){
if(tr[p].rev||~tr[p].tag||tr[p].addtag){
if(tr[p].l)tr[p].l=cpy(tr[p].l);
if(tr[p].r)tr[p].r=cpy(tr[p].r);
}
if(~tr[p].tag){
if(tr[p].l)update(tr[p].l,tr[p].tag);
if(tr[p].r)update(tr[p].r,tr[p].tag);
tr[p].tag=-1;
}
if(tr[p].addtag){
if(tr[p].l)add(tr[p].l,tr[p].addtag);
if(tr[p].r)add(tr[p].r,tr[p].addtag);
tr[p].addtag=0;
}
if(tr[p].rev){
if(tr[p].l)rever(tr[p].l);
if(tr[p].r)rever(tr[p].r);
tr[p].rev=0;
}
}
inline void split(int p,int k,int&x,int&y){
if(!p)x=y=0;
else{
pushdown(p);
if(tr[tr[p].l].size+1<=k){
x=cpy(p);
split(tr[x].r,k-tr[tr[x].l].size-1,tr[x].r,y);
pushup(x);
}else{
y=cpy(p);
split(tr[y].l,k,x,tr[y].l);
pushup(y);
}
}
}
inline int merge(int x,int y){
if(!x||!y)return x^y;
if(tr[x].fval<tr[y].fval){
pushdown(x);
tr[x].r=merge(tr[x].r,y);
pushup(x);
return x;
}else{
pushdown(y);
tr[y].l=merge(x,tr[y].l);
pushup(y);
return y;
}
}
inline void dfs(int p){
pushdown(p);
if(tr[p].l)dfs(tr[p].l);
cerr<<tr[p].val<<" ";
if(tr[p].r)dfs(tr[p].r);
}
inline void print(int p){
cerr<<p<<":";
dfs(p);
cerr<<endl;
}
int l,r,h;
#define mid ((l+r)>>1)
inline int build(int l,int r){
if(l>r)return 0;
int p=INSERT(a[mid]);
tr[p].l=build(l,mid-1);
tr[p].r=build(mid+1,r);
pushup(p);
return p;
}
inline void del(int x){
split(rt,x,l,r);
split(l,x-1,l,h);
h=merge(tr[h].l,tr[h].r);
rt=merge(merge(l,h),r);
}
inline int query(int x,int y){
split(rt,y,l,r);
split(l,x-1,l,h);
int res=tr[h].sum;
rt=merge(merge(l,h),r);
return res;
}
inline void modify(int x,int y,int k){
split(rt,y,l,r);
split(l,x-1,l,h);
update(h,k);
rt=merge(merge(l,h),r);
}
inline void Plus(int x,int y,int k){
split(rt,y,l,r);
split(l,x-1,l,h);
add(h,k);
rt=merge(merge(l,h),r);
}
inline void Copy(int x,int y,int X,int Y){
split(rt,y,l,r);
split(l,x-1,l,h);
int p=cpy(h);
rt=merge(merge(l,h),r);
split(rt,Y,l,r);
split(l,X-1,l,h);
rt=merge(merge(l,p),r);
}
inline void Swap(int x,int y,int X,int Y){
if(x>X)swap(x,X),swap(y,Y);
X-=y,Y-=y;
int L,R,H;
split(rt,y,l,r);
split(l,x-1,l,h);
split(r,Y,L,R);
split(L,X-1,L,H);
r=merge(merge(L,h),R);
rt=merge(merge(l,H),r);
}
inline void reverse(int x,int y){
split(rt,y,l,r);
split(l,x-1,l,h);
h=cpy(h);
rever(h);
rt=merge(merge(l,h),r);
}
int top;
inline void rebuild(int p){
pushdown(p);
if(tr[p].l)rebuild(tr[p].l);
a[++top]=tr[p].val;
if(tr[p].r)rebuild(tr[p].r);
}
}T;
int n,m;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
srand(19260817);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
T.rt=T.build(1,n);
for(int i=1,opt,x,y,l,r,k;i<=m;i++){
cin>>opt>>l>>r;
if(opt==1){
cout<<T.query(l,r)<<endl;
}else if(opt==2){
cin>>k;
T.modify(l,r,k);
}else if(opt==3){
cin>>k;
T.Plus(l,r,k);
}else if(opt==4){
cin>>x>>y;
T.Copy(l,r,x,y);
}else if(opt==5){
cin>>x>>y;
T.Swap(l,r,x,y);
}else{
T.reverse(l,r);
}
if(num>=3000000){
T.top=0;
T.rebuild(T.rt);
num=0;
T.rt=T.build(1,n);
}
// T.top=0;
// T.rebuild(T.rt);
// for(int j=1;j<=n;j++)cerr<<a[j]<<' ';
// cerr<<endl;
}
T.top=0;
T.rebuild(T.rt);
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
return 0;
}
```
by 灰鹤在此 @ 2022-04-08 19:15:22
你有可持久化吗?
by A1443356159 @ 2022-04-08 19:50:42
@[A1443356159](/user/79065) 原来是 Copy 那一段我没有可持久化啊
by 灰鹤在此 @ 2022-04-08 20:15:56
我知道了
by 灰鹤在此 @ 2022-04-08 20:16:09