GSS系列有一丝丝像…

只不过那个是线段树 这个是splay

翻转 插入 删除啥的就是普通的splay

合在一起了而已

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

struct Tree{

    int v,rev,sum,lmax,rmax,maxx,ch[2],fa,size,same;

    void init(){v=rev=sum=lmax=rmax=maxx=ch[0]=ch[1]=fa=0;size=1;same=-1001;}

}tr[505000];

int rubbish[500050],top,n,m,root;

char op[105];

void push_up(int x){

    tr[0].init();tr[0].size=0,tr[0].maxx=-0x3f3f3f3f;

    int lson=tr[x].ch[0],rson=tr[x].ch[1];

    tr[x].size=tr[lson].size+tr[rson].size+1;

    tr[x].sum=tr[lson].sum+tr[rson].sum+tr[x].v;

    tr[x].lmax=max(max(tr[lson].lmax,tr[lson].sum+tr[rson].lmax+tr[x].v),0);

    tr[x].rmax=max(max(tr[rson].rmax,tr[rson].sum+tr[lson].rmax+tr[x].v),0);

    tr[x].maxx=max(tr[lson].maxx,max(tr[rson].maxx,tr[lson].rmax+tr[rson].lmax+tr[x].v));

}

void push_down(int x){

    int lson=tr[x].ch[0],rson=tr[x].ch[1];

    if(tr[x].same!=-1001){

        tr[lson].same=tr[rson].same=tr[x].same;

        tr[lson].v=tr[rson].v=tr[x].same;

        tr[lson].sum=tr[lson].size*tr[x].same;

        tr[rson].sum=tr[rson].size*tr[x].same;

        if(tr[x].same>0){

            tr[lson].maxx=tr[lson].lmax=tr[lson].rmax=tr[lson].sum;

            tr[rson].maxx=tr[rson].lmax=tr[rson].rmax=tr[rson].sum;

        }

        else{

            tr[lson].lmax=tr[lson].rmax=tr[rson].lmax=tr[rson].rmax=0;

            tr[lson].maxx=tr[rson].maxx=tr[x].same;

        }

        tr[x].same=-1001;

    }

    if(tr[x].rev){

        tr[lson].rev^=1,tr[rson].rev^=1;

        swap(tr[x].ch[0],tr[x].ch[1]);

        swap(tr[lson].lmax,tr[lson].rmax);

        swap(tr[rson].lmax,tr[rson].rmax);

        tr[x].rev=0;

    }

}

void rotate(int p){

    int q=tr[p].fa,y=tr[q].fa,f=(tr[q].ch[1]==p);

    tr[q].ch[f]=tr[p].ch[!f];tr[tr[q].ch[f]].fa=q;

    tr[p].ch[!f]=q;tr[q].fa=p;tr[p].fa=y;

    if(y)tr[y].ch[tr[y].ch[1]==q]=p;

    push_up(q);

}

void splay(int x,int tp){

    for(int y;y=tr[x].fa;rotate(x)){

        if(y==tp)break;

        if(tr[y].fa!=tp){

            if((tr[y].ch[0]==x)^(tr[tr[y].fa].ch[0]==y))rotate(x);

            else rotate(y);

        }

    }push_up(x);

    if(!tp)root=x;

}

int newnode(){

    int temp=rubbish[top--];tr[temp].init();

    return temp;

}

int build(int l,int r,int fa){

    if(l>r)return 0;

    if(l==r){

        int temp=newnode();

        scanf("%d",&tr[temp].v);

        tr[temp].maxx=tr[temp].sum=tr[temp].v;

        tr[temp].lmax=tr[temp].rmax=max(0,tr[temp].v);

        tr[temp].fa=fa;

        return temp;

    }

    int mid=(l+r)>>1;

    int temp=newnode();

    tr[temp].ch[0]=build(l,mid-1,temp);

    scanf("%d",&tr[temp].v);

    tr[temp].maxx=tr[temp].sum=tr[temp].v;

    tr[temp].lmax=tr[temp].rmax=max(0,tr[temp].v);

    tr[temp].fa=fa;

    tr[temp].ch[1]=build(mid+1,r,temp);

    push_up(temp);

    return temp;

}

void check(int x){

    push_down(x);

    printf("x=%d lson=%d rson=%d sum=%d size=%d maxx=%d v=%d lmax=%d rmax=%d\n",x,tr[x].ch[0],tr[x].ch[1],tr[x].sum,tr[x].size,tr[x].maxx,tr[x].v,tr[x].lmax,tr[x].rmax);

    if(tr[x].ch[0])check(tr[x].ch[0]);

    if(tr[x].ch[1])check(tr[x].ch[1]);

}

int find(int x,int y){

    push_down(x);

    if(tr[tr[x].ch[0]].size+1==y)return x;

    if(tr[tr[x].ch[0]].size>=y)return find(tr[x].ch[0],y);

    else return find(tr[x].ch[1],y-tr[tr[x].ch[0]].size-1);

}

void dfs_del(int x){

    if(x)rubbish[++top]=x;

    if(tr[x].ch[0])dfs_del(tr[x].ch[0]);

    if(tr[x].ch[1])dfs_del(tr[x].ch[1]);

}

int main(){

    top=500000;

    for(int i=1;i<=500000;i++)rubbish[i]=i;

    scanf("%d%d",&n,&m);

    root=build(1,n,0);

    int tempa=find(root,1),tempb=newnode();

    splay(tempa,0);

    tr[tempa].ch[0]=tempb;tr[tempb].fa=tempa;

    push_up(tempa);

    tempa=find(root,n+1),tempb=newnode();

    splay(tempa,0);

    tr[tempa].ch[1]=tempb,tr[tempb].fa=tempa;

    push_up(tempa);

    while(m--){

        scanf("%s",op);

        int xx,yy,zz;

        if(op[0]=='I'){

            scanf("%d%d",&xx,&yy);

            tempa=find(root,xx+1);

            splay(tempa,0);

            tempb=find(root,xx+2);

            splay(tempb,tempa);

            int newroot=build(1,yy,tempb);

            tr[tempb].ch[0]=newroot;

            push_up(tempb);push_up(root);

        }

        else if(op[0]=='D'){

            scanf("%d%d",&xx,&yy);

            tempa=find(root,xx);

            splay(tempa,0);

            tempb=find(root,xx+1+yy);

            splay(tempb,tempa);

            dfs_del(tr[tempb].ch[0]);

            tr[tempb].ch[0]=0;push_up(tempb);push_up(tempa);

        }

        else if(op[2]=='K'){

            scanf("%d%d%d",&xx,&yy,&zz);

            tempa=find(root,xx);

            splay(tempa,0);

            tempb=find(root,xx+1+yy);

            splay(tempb,tempa);

            tr[tr[tempb].ch[0]].same=tr[tr[tempb].ch[0]].v=zz;

            push_down(tr[tempb].ch[0]),push_up(tr[tempb].ch[0]);

            push_up(tempb),push_up(tempa);

        }

        else if(op[0]=='R'){

            scanf("%d%d",&xx,&yy);

            tempa=find(root,xx);

            splay(tempa,0);

            tempb=find(root,xx+1+yy);

            splay(tempb,tempa);

            tr[tr[tempb].ch[0]].rev^=1;

            swap(tr[tr[tempb].ch[0]].lmax,tr[tr[tempb].ch[0]].rmax);

            push_up(tempb);

        }

        else if(op[0]=='G'){

            scanf("%d%d",&xx,&yy);

            tempa=find(root,xx);

            splay(tempa,0);

            tempb=find(root,xx+1+yy);

            splay(tempb,tempa);

            printf("%d\n",tr[tr[tempb].ch[0]].sum);

        }

        else{

            tempa=find(root,1);

            splay(tempa,0);

            tempb=find(root,tr[root].size);

            splay(tempb,tempa);

            printf("%d\n",tr[tr[tempb].ch[0]].maxx);

        }

    }

}