rt，TLE on #2-8 & #9，WA on #8。

调了一个下午加晚上了，实在调不出来了。

写的 splay，怀疑哪里写假了导致复杂度假了但是没找到。

#include <bits/stdc++.h>
#define lint __int128
// #define int long long
#define Rg register
#define Ri Rg int
#define Il inline
#define vec vector
#define pb push_back
#define fi first
#define se second
#define IT ::iterator
#define p_que priority_queue 

using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=5e5,Inf=1e9;
const db eps=1e-9,pi=acos(-1.0);

int n,siz,Q,a[N+5];
int id=0,rt=0,ch[N+5][2],sz[N+5],fa[N+5],va[N+5],xo[N+5],cv[N+5],mx[N+5],ml[N+5],mr[N+5],sm[N+5];
stack<int>dus;
queue<int>dq;

Il int getp(){
    if(!dus.empty()){
        int ret=dus.top();dus.pop();
        sz[ret]=fa[ret]=xo[ret]=mx[ret]=ml[ret]=mr[ret]=sm[ret]=va[ret]=0;
        return ret;
    }
    return ++id;
}

Il void pup(int p){
    sz[p]=sz[ch[p][0]]+sz[ch[p][1]]+1;
    ml[p]=max(sm[ch[p][0]]+va[p]+ml[ch[p][1]],ml[ch[p][0]]);
    mr[p]=max(sm[ch[p][1]]+va[p]+mr[ch[p][0]],mr[ch[p][1]]);
    mx[p]=max(max(mx[ch[p][0]],mx[ch[p][1]]),mr[ch[p][0]]+va[p]+ml[ch[p][1]]);
    sm[p]=sm[ch[p][0]]+sm[ch[p][1]]+va[p];
    return;
}

Il void pown(int p){
    if(xo[p]){
        xo[p]=0;swap(ch[p][0],ch[p][1]);
        xo[ch[p][0]]^=1,xo[ch[p][1]]^=1;
    }
    if(cv[p]!=Inf){
        xo[ch[p][0]]=xo[ch[p][1]]=0;
        if(ch[p][0]){
            va[ch[p][0]]=cv[ch[p][0]]=cv[p];sm[ch[p][0]]=sz[ch[p][0]]*cv[p];
            mx[ch[p][0]]=ml[ch[p][0]]=max(sm[ch[p][0]],0);
			mr[ch[p][0]]=max(sm[ch[p][0]],cv[p]);
        }
        if(ch[p][1]){
            va[ch[p][1]]=cv[ch[p][1]]=cv[p];sm[ch[p][1]]=sz[ch[p][1]]*cv[p];
            mx[ch[p][1]]=ml[ch[p][1]]=max(sm[ch[p][1]],0);
			mr[ch[p][1]]=max(sm[ch[p][1]],cv[p]);
        }
        cv[p]=Inf;
    }
    pup(p);
    return;
}

Il bool typ(int p){return ch[fa[p]][1]==p;}

Il void rot(int p){
    int fp=fa[p],ff=fa[fp];bool ty=typ(p);
    pown(fp),pown(p);
    ch[ff][typ(fp)]=p,fa[p]=ff;
    ch[fp][ty]=ch[p][!ty],fa[ch[p][!ty]]=fp;
    ch[p][!ty]=fp,fa[fp]=p;
    pup(fp),pup(p);
    return;
}

Il void splay(int p,int to){
    for(;fa[p]^to;rot(p))if(fa[fa[p]]^to)rot(typ(p)^typ(fa[p])?p:fa[p]);
    if(!to)rt=p;
    return;
}

Il int build(int l,int r,int fr){
    if(l>r)return 0;
    int p=getp(),mid=(l+r)>>1;
    sz[p]=1,ml[p]=mr[p]=mx[p]=va[p]=a[mid],fa[p]=fr,cv[p]=Inf;
    ch[p][0]=build(l,mid-1,p),ch[p][1]=build(mid+1,r,p);pup(p);
    return p;
}

Il int kth(int K){
    int p=rt;if(sz[p]<K)return -1;
    while(1){
        pown(p);
        if(sz[ch[p][0]]>=K)p=ch[p][0];
        else if(sz[ch[p][0]]+1==K){splay(p,0);return p;}
        else K-=sz[ch[p][0]]+1,p=ch[p][1];
    }
    return -1;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>Q;for(Ri i=2;i<=n+1;i++)cin>>a[i];rt=build(1,n+2,0);
    while(Q--){
        string op;cin>>op;
        if(op[2]=='S'){//INSERT
            int ps,m;cin>>ps>>m;for(Ri i=1;i<=m;i++)cin>>a[i];if(!m)continue;
            int tmp=build(1,m,0),lp=kth(ps+1),rp=ch[lp][1];
            while(ch[rp][0])rp=ch[rp][0];
            pown(rp);ch[rp][0]=tmp,fa[tmp]=rp,pup(rp),splay(tmp,0);
        }else if(op[2]=='L'){//DELETE
            int ps,m;cin>>ps>>m;if(!m)continue;
            int rp=kth(ps+m+1),lp=kth(ps);splay(rp,lp);
            dq.push(ch[rp][0]);
            while(!dq.empty()){
                int fq=dq.front();dq.pop();
                ch[fa[fq]][typ(fq)]=0;
                if(ch[fq][0])dq.push(ch[fq][0]);
                if(ch[fq][1])dq.push(ch[fq][1]);
                ch[fq][0]=ch[fq][1]=0;dus.push(fq);
            }
            pup(rp);splay(rp,0);
        }else if(op[2]=='K'){//COVER
            int ps,m,cov;cin>>ps>>m>>cov;if(!m)continue;
            int rp=kth(ps+m+1),lp=kth(ps);splay(rp,lp);int p=ch[rp][0];
            va[p]=cv[p]=cov,sm[p]=cov*sz[p];mx[p]=ml[p]=mr[p]=max(sm[p],0);xo[p]=0;
            splay(p,0);
        }else if(op[2]=='V'){//REVERSE
            int ps,m;cin>>ps>>m;if(!m)continue;
            int rp=kth(ps+m+1),lp=kth(ps);splay(rp,lp);int p=ch[rp][0];
            if(cv[p]==Inf){
                ml[p]=max(ml[ch[p][!xo[p]]],sm[ch[p][!xo[p]]]+va[p]+ml[ch[p][xo[p]]]);
                mr[p]=max(mr[ch[p][xo[p]]],sm[ch[p][xo[p]]]+va[p]+mr[ch[p][!xo[p]]]);
                mx[p]=max(max(mx[ch[p][0]],mx[ch[p][1]]),ml[ch[p][xo[p]]]+va[p]+mr[ch[p][!xo[p]]]);
            }
            xo[p]^=1;splay(p,0);
        }else if(op[2]=='T'){//TOTAL_SUM
            int ps,m;cin>>ps>>m;if(!m){cout<<"0\n";continue;}
            int rp=kth(ps+m+1),lp=kth(ps);splay(rp,lp);
            cout<<sm[ch[rp][0]]<<'\n';splay(ch[rp][0],0);
        }else cout<<mx[rt]<<'\n';//MAX_SUM
        // cout<<"CHECK:"<<sz[rt]<<'\n';
    }
    // for(Ri i=1;i<=sz[rt];i++)cout<<va[kth(i)]<<' ';
	return 0;
}

虽然但是真的会有人调大 ds 吗（。