[NOI2005]维护数列 恶心到毁天灭地的splay

#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<vector>
#include<iostream>
#define ll long long
#define re register
#define inf 0x7f7f7f7f
#define inl inline
#define sqr(x) (x*x)
#define max(a,b) (a>b?a:b)
//#define eps 1e-8
#define debug puts("**************************");
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
using namespace std;
//const ll mod;
const ll MAXN=1e6+10;
inl ll read() {
    re ll x = 0; re int f = 1;
    char ch = getchar();
    while(ch<‘0‘||ch>‘9‘) { if(ch== ‘-‘ ) f = -1; ch = getchar(); }
    while(ch>=‘0‘&&ch<=‘9‘) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x * f;
}
inl char readc() {
    char ch=getchar();
    while((‘z‘<ch||ch<‘a‘)&&(‘Z‘<ch||ch<‘A‘)) ch=getchar();
    return ch;
}
inl void write(re ll x){
    if(x>=10)write(x/10);
    putchar(x%10+‘0‘);
}
inl void writeln(re ll x){
    if(x<0) {x=-x;putchar(‘-‘);}
    write(x); puts("");
}
inl ll gcd(re ll x,re ll y){while(y^=x^=y^=x%=y);return x;}
inl ll Lcm(re ll a,re ll b) {return a/gcd(a,b)*b;}
inl void FR() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
inl void FC() {
    fclose(stdin);
    fclose(stdout);
}
ll root,id[MAXN],cnt;
struct Node {
    ll fa,son[2],sumx,val,siz,maxx,lx,rx;
    bool rev,flag;
    void clear() {
        fa=son[0]=son[1]=sumx=val=siz=maxx=lx=rx=rev=flag=0;
    }
}Tree[MAXN];
ll dir(ll x) {return Tree[Tree[x].fa].son[1]==x;}
inl void pushup(ll x) {
    re ll l=Tree[x].son[0],r=Tree[x].son[1];
    Tree[x].siz=Tree[l].siz+Tree[r].siz+1;
    Tree[x].sumx=Tree[l].sumx+Tree[r].sumx+Tree[x].val;
    Tree[x].maxx=max(Tree[r].maxx,Tree[l].maxx);
    Tree[x].maxx=max(Tree[x].maxx,Tree[l].rx+Tree[r].lx+Tree[x].val);
    Tree[x].lx=max(Tree[l].lx,Tree[l].sumx+Tree[x].val+Tree[r].lx);
    Tree[x].rx=max(Tree[r].rx,Tree[r].sumx+Tree[x].val+Tree[l].rx);
}
inl void pushdown(ll x) {
    re ll l=Tree[x].son[0],r=Tree[x].son[1];
    if(Tree[x].flag) {
        Tree[x].flag=Tree[x].rev=0;
        if(l) Tree[l].val=Tree[x].val,Tree[l].sumx=Tree[l].val*Tree[l].siz,Tree[l].flag=1;
        if(r) Tree[r].val=Tree[x].val,Tree[r].sumx=Tree[r].val*Tree[r].siz,Tree[r].flag=1;
        if(Tree[x].val>=0) {
            if(l) Tree[l].lx=Tree[l].rx=Tree[l].maxx=Tree[l].sumx;
            if(r) Tree[r].lx=Tree[r].rx=Tree[r].maxx=Tree[r].sumx;
        }
        else {
            if(l) Tree[l].lx=Tree[l].rx=0,Tree[l].maxx=Tree[l].val;
            if(r) Tree[r].lx=Tree[r].rx=0,Tree[r].maxx=Tree[r].val;
        }
    }
    if(Tree[x].rev) {
        Tree[x].rev=0;Tree[l].rev^=1;Tree[r].rev^=1;
        swap(Tree[l].lx,Tree[l].rx);swap(Tree[r].lx,Tree[r].rx);
        swap(Tree[l].son[0],Tree[l].son[1]);
        swap(Tree[r].son[0],Tree[r].son[1]);
    }
}
inl void rotate(ll x) {
    re ll y=Tree[x].fa,z=Tree[y].fa,o=dir(x);
    re ll so=dir(y);
    Tree[y].son[o]=Tree[x].son[o^1];
    Tree[Tree[y].son[o]].fa=y;
    Tree[x].son[o^1]=y;
    Tree[y].fa=x;
    Tree[z].son[so]=x;
    Tree[x].fa=z;
    pushup(y);pushup(x);
}
inl void splay(ll x,ll goal) {
    for(re ll y;(y=Tree[x].fa)!=goal;rotate(x)) {
        if(Tree[y].fa!=goal) rotate(dir(y)==dir(x)?y:x);
    }
    if(!goal) root=x;
}
inl ll find(ll x,ll rk) {
    pushdown(x);
    re ll l=Tree[x].son[0],r=Tree[x].son[1];
    if(Tree[l].siz+1==rk) return x;
    else if(Tree[l].siz>=rk) return find(l,rk);
    else return find(r,rk-Tree[l].siz-1);
}
ll s[MAXN];
inl ll build(ll l,ll r,ll fro) {
    re ll mid=(l+r)>>1,t=id[mid];
    Tree[t].clear();
    Tree[t].val=s[mid];
    Tree[t].fa=fro;
    if(l==r) {
        Tree[t].lx=Tree[t].rx=max(0,Tree[t].val);
        Tree[t].maxx=Tree[t].sumx=Tree[t].val;
        Tree[t].son[0]=Tree[t].son[1]=0;
        Tree[t].siz=1;
        return t;
    }
    if(l<mid) Tree[t].son[0]=build(l,mid-1,t);
    else Tree[t].son[0]=0;
    if(mid<r) Tree[t].son[1]=build(mid+1,r,t);
    else Tree[t].son[1]=0;
    pushup(t);
    return t;
}
char ss[20];
queue<ll>Q;
inl void insert(ll pos,ll tot) {
    for(re ll i=1;i<=tot;i++) s[i]=read();
    for(re ll i=1;i<=tot;i++) {
        if(!Q.empty()) id[i]=Q.front(),Q.pop();
        else id[i]=++cnt;
    }
    re ll l=find(root,pos+1),r=find(root,pos+2);
    splay(l,0);splay(r,l);
    Tree[r].son[0]=build(1,tot,r);
    pushup(r);pushup(l);
}
inl void recycle(ll x) {
    re ll &l=Tree[x].son[0],&r=Tree[x].son[1];
    if(l) recycle(l);
    if(r) recycle(r);
    Q.push(x);
    Tree[x].clear();l=r=0;
}
inl ll split(ll pos,ll tot) {
    re ll x=find(root,pos),y=find(root,pos+tot+1);
    splay(x,0);splay(y,x);
    return Tree[y].son[0];
}
inl void del(ll pos,ll tot) {
    re ll x=split(pos,tot),y=Tree[x].fa;
    recycle(x);Tree[y].son[0]=0;
    pushup(y);pushup(Tree[y].fa);
}
inl void modify(ll pos,ll tot,ll val) {
    re ll x=split(pos,tot),y=Tree[x].fa;
    Tree[x].flag=1;
    Tree[x].val=val,Tree[x].sumx=Tree[x].siz*Tree[x].val;
    if(Tree[x].val>=0) Tree[x].lx=Tree[x].rx=Tree[x].maxx=Tree[x].sumx;
    else Tree[x].lx=Tree[x].rx=0,Tree[x].maxx=Tree[x].val;
    pushup(y);pushup(Tree[y].fa);
}
inl void rever(ll pos,ll tot) {
    re ll x=split(pos,tot),y=Tree[x].fa;
    if(!Tree[x].flag) {
        Tree[x].rev^=1;
        swap(Tree[x].lx,Tree[x].rx);
        swap(Tree[x].son[0],Tree[x].son[1]);
        pushup(y);pushup(Tree[y].fa);
    }
}
inl ll query(ll pos,ll tot) {
    re ll x=split(pos,tot);
    return Tree[x].sumx;
}
int main() {
//  FR();
    re ll n=read(),m=read();
    for(re ll i=1;i<=n;i++) {s[i+1]=read();}
    Tree[0].maxx=s[1]=s[n+2]=-inf;cnt=n+2;
    for(re ll i=1;i<=n+2;i++) id[i]=i;
    root=build(1,n+2,0);
    for(re ll i=1;i<=m;i++) {
        scanf("%s",ss);
        if(ss[0]==‘I‘) {
            re ll pos=read(),tot=read();
            insert(pos,tot);
        }
        else if(ss[0]==‘D‘) {
            re ll pos=read(),tot=read();
            del(pos,tot);
        }
        else if(ss[0]==‘M‘) {
            if(ss[2]==‘X‘) writeln(Tree[root].maxx);
            else {
                re ll pos=read(),tot=read(),val=read();
                modify(pos,tot,val);
            }
        }
        else if(ss[0]==‘R‘) {
            re ll pos=read(),tot=read();
            rever(pos,tot);
        }
        else if(ss[0]==‘G‘) {
            re ll pos=read(),tot=read();
            writeln(query(pos,tot));
        }
    }
//  FC();
    return 0;
}