其实就是一道题占坑啦
[NOI2005]维护数列
分析：
每次操作都要 \(Splay\) 一下
\(Insert\) 操作：重建一棵平衡树，把 \(l\) 变成根，\(l+2\) 变成右子树的根，那棵平衡树就挂在 \(l+2\) 的左子树下
\(Delete\) 操作：直接将其左子树删掉
\(Make-Same\) 操作：把整个区间打一个标记，每次 \(pushdown\) 就好了
\(Reverse\) 操作：类似 \(Make-Same\) 操作
\(Get-Sum\) 操作：直接输出 \(sum\)
\(Max-Sum\) 操作：记 \(Max,lmax,rmax\)，每次 \(pushup\) 和 \(pushdown\) 的时候弄一下就好了
\(Code\ Below:\)
#include <bits/stdc++.h>
using namespace std;
const int maxn=6000000+10;
const int inf=0x3f3f3f3f;
int n,m,a[maxn],ch[maxn][2],fa[maxn],key[maxn],siz[maxn],sum[maxn],Max[maxn],lmax[maxn],rmax[maxn],rt,sz;
bool rev[maxn],tag[maxn];
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void pushup(int x){
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];
Max[x]=max(rmax[ch[x][0]]+key[x]+lmax[ch[x][1]],max(Max[ch[x][0]],Max[ch[x][1]]));
lmax[x]=max(lmax[ch[x][0]],sum[ch[x][0]]+key[x]+lmax[ch[x][1]]);
rmax[x]=max(rmax[ch[x][1]],rmax[ch[x][0]]+key[x]+sum[ch[x][1]]);
}
inline void pushdown(int x){
if(tag[x]){
key[ch[x][0]]=key[ch[x][1]]=key[x];
sum[ch[x][0]]=siz[ch[x][0]]*key[x];
sum[ch[x][1]]=siz[ch[x][1]]*key[x];
if(ch[x][0]) Max[ch[x][0]]=max(key[x],sum[ch[x][0]]);
if(ch[x][1]) Max[ch[x][1]]=max(key[x],sum[ch[x][1]]);
lmax[ch[x][0]]=rmax[ch[x][0]]=max(0,sum[ch[x][0]]);
lmax[ch[x][1]]=rmax[ch[x][1]]=max(0,sum[ch[x][1]]);
tag[ch[x][0]]=tag[ch[x][1]]=1;tag[x]=rev[x]=0;
}
if(rev[x]){
swap(lmax[ch[x][0]],rmax[ch[x][0]]);
swap(lmax[ch[x][1]],rmax[ch[x][1]]);
swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);
swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);
rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]=0;
}
}
inline void rotate(int x){
int y=fa[x],z=fa[y],k=(x==ch[y][1]);
ch[y][k]=ch[x][k^1];fa[ch[x][k^1]]=y;
ch[x][k^1]=y;fa[y]=x;fa[x]=z;
if(z) ch[z][ch[z][1]==y]=x;
pushup(y);pushup(x);
}
inline void splay(int x,int z){
for(int y;(y=fa[x])!=z;rotate(x))
if(fa[y]!=z) rotate((x==ch[y][1])^(y==ch[z][1])?x:y);
if(!z) rt=x;
}
inline int findkth(int x,int k){
while(1){
pushdown(x);
if(k<=siz[ch[x][0]]) x=ch[x][0];
else {
k-=siz[ch[x][0]]+1;
if(!k) return x;
x=ch[x][1];
}
}
}
inline int split(int l,int r){
l=findkth(rt,l);r=findkth(rt,r);
splay(l,0);splay(r,l);
return ch[r][0];
}
inline int query(int l,int r){
return sum[split(l,r)];
}
inline void modify(int l,int r,int v){
int x=split(l,r),y=fa[x],z=fa[y];
key[x]=v;tag[x]=1;sum[x]=siz[x]*key[x];
Max[x]=max(key[x],sum[x]);
lmax[x]=rmax[x]=max(0,sum[x]);
pushup(y);pushup(z);
}
inline void reverse(int l,int r){
int x=split(l,r),y=fa[x],z=fa[y];
if(!tag[x]){
rev[x]^=1;
swap(lmax[x],rmax[x]);
swap(ch[x][0],ch[x][1]);
pushup(y);pushup(z);
}
}
inline void erase(int l,int r){
int x=split(l,r),y=fa[x],z=fa[y];
ch[y][0]=0;pushup(y);pushup(z);
}
int build(int l,int r,int f){
int mid=(l+r)>>1,x=++sz;
if(l==r){
siz[x]=1;sum[x]=Max[x]=a[l];
lmax[x]=rmax[x]=max(0,a[l]);
}
if(l<mid) ch[x][0]=build(l,mid-1,x);
if(mid<r) ch[x][1]=build(mid+1,r,x);
key[x]=a[mid];fa[x]=f;pushup(x);
return x;
}
inline void insert(int l,int r){
for(int i=1;i<=r;i++) a[i]=read();
int z=build(1,r,0),x=findkth(rt,l+1),y=findkth(rt,l+2);
splay(x,0);splay(y,x);
fa[z]=y;ch[y][0]=z;
pushup(y);pushup(x);
}
int main()
{
n=read(),m=read();
Max[0]=a[1]=a[n+2]=-inf;
for(int i=2;i<=n+1;i++) a[i]=read();
rt=build(1,n+2,0);
char op[20];int pos,tot,val;
while(m--){
scanf("%s",op);
if(op[0]=='I'){
pos=read(),tot=read();
insert(pos,tot);
}
if(op[0]=='D'){
pos=read(),tot=read();
erase(pos,pos+tot+1);
}
if(op[0]=='M'){
if(op[2]=='K'){
pos=read(),tot=read(),val=read();
modify(pos,pos+tot+1,val);
}
else printf("%d\n",Max[rt]);
}
if(op[0]=='R'){
pos=read(),tot=read();
reverse(pos,pos+tot+1);
}
if(op[0]=='G'){
pos=read(),tot=read();
printf("%d\n",query(pos,pos+tot+1));
}
}
return 0;
}