浅谈(splay)：https://www.cnblogs.com/AKMer/p/9979592.html
浅谈(fhq)_(treap)：https://www.cnblogs.com/AKMer/p/9981274.html
题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=1500
究极无敌大模板题，记得要写垃圾回收。
时间复杂度：(O((n+m)logn))
空间复杂度：(O(n))
(splay)代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=5e5+5,inf=1e9;
char s[20];
int a[maxn];
int n,m,pos,tot;
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
struct Splay {
int root;
int dust[maxn],top;
int val[maxn],sum[maxn];
bool rev[maxn],cov[maxn];
int mx[maxn],lmx[maxn],rmx[maxn];
int siz[maxn],fa[maxn],son[maxn][2];
void clear(int u) {
rev[u]=cov[u]=0;
son[u][0]=son[u][1]=0;
}
void update(int u) {
int ls=son[u][0],rs=son[u][1];
siz[u]=siz[ls]+1+siz[rs];
sum[u]=sum[ls]+val[u]+sum[rs];
lmx[u]=max(lmx[ls],sum[ls]+val[u]+lmx[rs]);
rmx[u]=max(rmx[rs],sum[rs]+val[u]+rmx[ls]);
mx[u]=max(max(mx[ls],mx[rs]),rmx[ls]+val[u]+lmx[rs]);
}
int build(int l,int r,int lst) {
if(r<l)return 0;
if(l==r) {
int id=dust[top--];
siz[id]=1,fa[id]=lst;
lmx[id]=rmx[id]=max(0,a[l]);
val[id]=sum[id]=mx[id]=a[l];
return id;
}
int mid=(l+r)>>1,id=dust[top--];
val[id]=a[mid],fa[id]=lst;
son[id][0]=build(l,mid-1,id);
son[id][1]=build(mid+1,r,id);
update(id);return id;
}
void prepare() {
mx[0]=-inf;
for(int i=1;i<=500002;i++)
dust[++top]=i;
root=build(1,n+2,0);
}
void make_cov_tag(int u,int v) {
if(!u)return;
cov[u]=1,val[u]=v,sum[u]=siz[u]*v;
if(v>0)lmx[u]=rmx[u]=mx[u]=siz[u]*v;
else lmx[u]=rmx[u]=0,mx[u]=v;
}
void make_rev_tag(int u) {
if(!u)return;
swap(lmx[u],rmx[u]);
rev[u]^=1,swap(son[u][0],son[u][1]);
}
void push_down(int u) {
if(cov[u]) {
make_cov_tag(son[u][0],val[u]);
make_cov_tag(son[u][1],val[u]);
cov[u]=0;
}
if(rev[u]) {
make_rev_tag(son[u][0]);
make_rev_tag(son[u][1]);
rev[u]=0;
}
}
int find(int u,int rk) {
push_down(u);
if(siz[son[u][0]]+1==rk)return u;
if(siz[son[u][0]]>=rk)return find(son[u][0],rk);
return find(son[u][1],rk-siz[son[u][0]]-1);
}
int t(int u) {return son[fa[u]][1]==u;}
void rotate(int u) {
int ret=t(u),f=fa[u],s=son[u][ret^1];
son[f][ret]=s;if(s)fa[s]=f;son[u][ret^1]=f;
fa[u]=fa[f];if(fa[f])son[fa[f]][t(f)]=u;
fa[f]=u;update(f),update(u);
}
void splay(int goal,int u) {
int tmp=fa[goal];
while(fa[u]!=tmp) {
if(fa[fa[u]]!=tmp) {
if(t(fa[u])==t(u))rotate(fa[u]);
else rotate(u);
}
rotate(u);
}
if(!tmp)root=u;
}
void recycle(int u) {
if(!u)return;
dust[++top]=u;
recycle(son[u][0]);
recycle(son[u][1]);
clear(u);
}
void ins(int pos) {
for(int i=1;i<=tot;i++)a[i]=read();
int u1=find(root,pos),u2=find(root,pos+1);
splay(root,u1),splay(son[u1][1],u2);
son[u2][0]=build(1,tot,u2);
update(u2),update(u1);
}
void del(int l,int r) {
int u1=find(root,l-1),u2=find(root,r+1);
splay(root,u1),splay(son[u1][1],u2);
int tmp=son[u2][0];
son[u2][0]=fa[tmp]=0;
recycle(tmp);
update(u2),update(u1);
}
void cover(int l,int r,int v) {
int u1=find(root,l-1),u2=find(root,r+1);
splay(root,u1),splay(son[u1][1],u2);
make_cov_tag(son[u2][0],v);
update(u2),update(u1);
}
void rever(int l,int r) {
int u1=find(root,l-1),u2=find(root,r+1);
splay(root,u1),splay(son[u1][1],u2);
make_rev_tag(son[u2][0]);
update(u2),update(u1);
}
int query(int l,int r) {
int u1=find(root,l-1),u2=find(root,r+1);
splay(root,u1),splay(son[u1][1],u2);
return sum[son[u2][0]];
}
}T;
int main() {
n=read(),m=read();
for(int i=2;i<=n+1;i++)
a[i]=read();
a[1]=a[n+2]=-inf,T.prepare();
for(int i=1;i<=m;i++) {
scanf("%s",s+1);
if(s[1]!='M'||s[4]!='-')
pos=read()+1,tot=read();
if(s[1]=='I')T.ins(pos);
if(s[1]=='D')T.del(pos,pos+tot-1);
if(s[1]=='M'&&s[4]=='E') {
int c=read();
T.cover(pos,pos+tot-1,c);
}
if(s[1]=='R')T.rever(pos,pos+tot-1);
if(s[1]=='G')printf("%d
",T.query(pos,pos+tot-1));
if(s[1]=='M'&&s[4]=='-')printf("%d
",T.mx[T.root]);
}
return 0;
}
(fhq)_(treap)版代码如下：
#include <ctime>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int maxn=5e5+5,inf=1e9;
char s[20];
int a[maxn];
int n,m,pos,tot;
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
struct fhq_treap {
int root,top;
int dust[maxn];
bool cov[maxn],rev[maxn];
int fix[maxn],son[maxn][2];
int mx[maxn],lmx[maxn],rmx[maxn];
int val[maxn],sum[maxn],siz[maxn];
void update(int u) {
int ls=son[u][0],rs=son[u][1];
siz[u]=siz[ls]+1+siz[rs];
sum[u]=sum[ls]+val[u]+sum[rs];
lmx[u]=max(lmx[ls],sum[ls]+val[u]+lmx[rs]);
rmx[u]=max(rmx[rs],sum[rs]+val[u]+rmx[ls]);
mx[u]=max(max(mx[ls],mx[rs]),rmx[ls]+val[u]+lmx[rs]);
}
int build(int l,int r) {
if(r<l)return 0;
if(l==r) {
int id=dust[top--];
fix[id]=rand(),siz[id]=1;
mx[id]=val[id]=sum[id]=a[l];
lmx[id]=rmx[id]=max(0,a[l]);
return id;
}
int mid=(l+r)>>1,id=dust[top--];
fix[id]=rand(),val[id]=a[mid];
son[id][0]=build(l,mid-1);
son[id][1]=build(mid+1,r);
update(id);return id;
}
void prepare() {
mx[0]=-inf;
for(int i=1;i<=500000;i++)
dust[++top]=i;
root=build(1,n);
}
void make_cov_tag(int u,int v) {
if(!u)return;
cov[u]=1,val[u]=v,sum[u]=siz[u]*v;
if(v>0)mx[u]=lmx[u]=rmx[u]=sum[u];
else mx[u]=v,lmx[u]=rmx[u]=0;
}
void make_rev_tag(int u) {
if(!u)return;
rev[u]^=1,swap(lmx[u],rmx[u]);
swap(son[u][0],son[u][1]);
}
void push_down(int u) {
if(cov[u]) {
make_cov_tag(son[u][0],val[u]);
make_cov_tag(son[u][1],val[u]);
cov[u]=0;
}
if(rev[u]) {
make_rev_tag(son[u][0]);
make_rev_tag(son[u][1]);
rev[u]=0;
}
}
pii split(int u,int rk) {
if(!rk)return make_pair(0,u);
if(rk==siz[u])return make_pair(u,0);
push_down(u);
if(siz[son[u][0]]>=rk) {
pii tmp=split(son[u][0],rk);
son[u][0]=tmp.second,update(u);
return make_pair(tmp.first,u);
}
else {
pii tmp=split(son[u][1],rk-siz[son[u][0]]-1);
son[u][1]=tmp.first,update(u);
return make_pair(u,tmp.second);
}
}
int merge(int a,int b) {
if(!a||!b)return a+b;
push_down(a),push_down(b);
if(fix[a]>fix[b])return son[a][1]=merge(son[a][1],b),update(a),a;
else return son[b][0]=merge(a,son[b][0]),update(b),b;
}
void ins(int pos) {
for(int i=1;i<=tot;i++)
a[i]=read();
pii tmp=split(root,pos);
root=merge(merge(tmp.first,build(1,tot)),tmp.second);
}
void recycle(int u) {
if(!u)return;
dust[++top]=u;
recycle(son[u][0]),recycle(son[u][1]);
son[u][0]=son[u][1]=0,rev[u]=cov[u]=0;
}
void del(int l,int r) {
pii tmp1=split(root,r);
pii tmp2=split(tmp1.first,l-1);
root=merge(tmp2.first,tmp1.second);
recycle(tmp2.second);
}
void cover(int l,int r) {
int v=read();
pii tmp1=split(root,r);
pii tmp2=split(tmp1.first,l-1);
make_cov_tag(tmp2.second,v);
root=merge(merge(tmp2.first,tmp2.second),tmp1.second);
}
void rever(int l,int r) {
pii tmp1=split(root,r);
pii tmp2=split(tmp1.first,l-1);
make_rev_tag(tmp2.second);
root=merge(merge(tmp2.first,tmp2.second),tmp1.second);
}
int query(int l,int r) {
pii tmp1=split(root,r);
pii tmp2=split(tmp1.first,l-1);
int res=sum[tmp2.second];
root=merge(merge(tmp2.first,tmp2.second),tmp1.second);
return res;
}
}T;
int main() {
srand(time(0));
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read();
T.prepare();
for(int i=1;i<=m;i++) {
scanf("%s",s+1);
if(s[1]!='M'||s[4]!='-')
pos=read(),tot=read();
if(s[1]=='I')T.ins(pos);
if(s[1]=='D')T.del(pos,pos+tot-1);
if(s[1]=='M'&&s[4]=='E')T.cover(pos,pos+tot-1);
if(s[1]=='R')T.rever(pos,pos+tot-1);
if(s[1]=='G')printf("%d
",T.query(pos,pos+tot-1));
if(s[1]=='M'&&s[4]=='-')printf("%d
",T.mx[T.root]);
}
return 0;
}