Splay维护序列

/*
 * @Author: luxin 
 * @Date: 2020-02-08 14:43:55 
 * @Last Modified by: luxin
 * @Last Modified time: 2020-02-20 20:37:51
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
#define I inline
#define R register
#define inf 107374282
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
#define maxn 1000010
#define tagnone 10000110
int a[maxn],n,m;
struct luna{
    int child[2],parent,size,sum,value,left,right,mid,rev,tag;
    I void clear(){child[1]=child[0]=parent=value=rev=0,tag=tagnone;}
}tr[maxn];
#define ls tr[o].child[0]
#define rs tr[o].child[1]
int id[maxn],cnt,rub[maxn],top,root;
I int rubbish(){
    return top?rub[top--]:++cnt;
}
I void change_value(int o,int val){
    if(!o)return;
    tr[o].tag=tr[o].value=val,
    tr[o].sum=val*tr[o].size,
    tr[o].left=tr[o].right=max(0,tr[o].sum),
    tr[o].mid=max(tr[o].sum,tr[o].value);
}
I void change_rev(int o){
    swap(ls,rs);
    swap(tr[o].left,tr[o].right);
    tr[o].rev^=1;
}
I void pushup(int o){
    luna&x=tr[ls],
        &y=tr[rs],
        &res=tr[o];
    res.sum=x.sum+y.sum+res.value;
    res.size=x.size+y.size+1;
    res.right=max(y.right,x.right+res.value+y.sum);
    res.left=max(x.left,y.left+res.value+x.sum);
    res.mid=max(max(x.mid,y.mid),x.right+y.left+res.value);
}
I void pushdown(int o){
    if(tr[o].tag!=tagnone){
        change_value(ls,tr[o].tag);
        change_value(rs,tr[o].tag);
        tr[o].tag=tagnone;
    }
    if(tr[o].rev){
        change_rev(ls);
        change_rev(rs);
        tr[o].rev=0;
    }
}
I bool identify(int o){
    return tr[tr[o].parent].child[1]==o;
}
I void connect(int o,int pa,bool flag){
    tr[o].parent=pa;
    tr[pa].child[flag]=o;
}
I void rotate(int x){
    int y=tr[x].parent;
    int r=tr[y].parent;
    bool flag_x=identify(x);
    bool flag_y=identify(y);
    int b=tr[x].child[!flag_x];
    connect(b,y,flag_x);
    connect(y,x,!flag_x);
    connect(x,r,flag_y);
    pushup(y),pushup(x);
}
I void splay(int at,int to){
    while(tr[at].parent!=to){
        int pa=tr[at].parent;
        if(tr[pa].parent!=to)
            identify(at)==identify(pa)?rotate(pa):rotate(at);
            rotate(at);
    }
    if(!to)root=at;
}
I void New(int o,int val){
    tr[o].mid=tr[o].sum=val;
    tr[o].tag=tagnone;
    tr[o].rev=0;
    tr[o].left=tr[o].right=max(val,0);
    tr[o].size=1;
    tr[o].value=val;
}
I void build(int l,int r,int fa){
    int mid=(l+r)>>1;
    int o=id[mid],pre=id[fa];
    if(l==r)New(o,a[l]);
    if(l<mid)build(l,mid-1,mid);
    if(r>mid)build(mid+1,r,mid);
    tr[o].value=a[mid],tr[o].parent=pre,tr[o].tag=tagnone;
    pushup(o);
    tr[pre].child[mid>=fa]=o;
}
I int kth(int x){
    int o=root;
    while(233){
        pushdown(o);
        if(tr[ls].size>=x)o=ls;
        else{
            if(tr[ls].size+1==x)return o;
            else x-=tr[ls].size+1,o=rs;
        }
    }
    return inf;
}
I void remove(int o){
    if(ls)remove(ls);
    if(rs)remove(rs);
    rub[++top]=o;
    tr[o].clear();
}
I int split(int k,int len){
    int x=kth(k),y=kth(k+len+1);
    splay(x,0),splay(y,x);
    return tr[y].child[0];
}
I void query(int k,int len){
    int node=split(k,len);
    printf("%d\n",tr[node].sum);
}
I void update(int x,int len,int val){
    int o=split(x,len);
    int y=tr[o].parent;
    change_value(o,val);
    pushup(y),pushup(tr[y].parent);
}
I void reverse(int x,int len){   
    int o=split(x,len);
    int y=tr[o].parent;
    change_rev(o);
    pushup(y),pushup(tr[y].parent);
}
I void eraser(int x,int len){
    int o=split(x,len);
    int y=tr[o].parent;
    remove(o);
    tr[y].child[0]=0;
    pushup(y),pushup(tr[y].parent);
}
I void insert(int k,int len){
    for(int i=1;i<=len;++i)
        scanf("%d",&a[i]),
        id[i]=rubbish();
    build(1,len,0);
    int z=id[(1+len)>>1];
    int x=kth(k+1),y=kth(k+2);
    splay(x,0),splay(y,x);
    tr[y].child[0]=z;
    tr[z].parent=y;
    pushup(y),pushup(tr[y].parent);
}
#define online
signed main(){
#ifndef online
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif
    scanf("%d%d",&n,&m);
    tr[0].mid=a[1]=a[n+2]=-inf;
    for(int i=1;i<=n;++i)scanf("%d",&a[i+1]);
    for(int i=1;i<=n+2;++i)id[i]=i;
    build(1,n+2,0);
    root=(n+3)>>1;
    cnt=n+2;
    for(int i=1;i<=m;++i){
        string s;int x,len,y;
        cin>>s;
        if(s!="MAX-SUM")scanf("%d%d",&x,&len);
        else printf("%d\n",tr[root].mid);
        if(s=="INSERT")insert(x,len);
        if(s=="DELETE")eraser(x,len);
        if(s=="MAKE-SAME")
            scanf("%d",&y),update(x,len,y);
        if(s=="REVERSE")reverse(x,len);
        if(s=="GET-SUM")query(x,len);
    }
    return 0;
}