1. 题目

传送门=￣ω￣=

大概就是这样：

需要每单个操作（插入、删除算多次操作）$log_2N$以下

2. 题解

丧心病狂の模板题，，，

mmp 调了我三天

主要是这题细节好多的，比如要注意翻转儿子要先下传再打标记（和我以前做法不同）。

具体做法就和线段树（静态）的做法一样，维护左右最大的两边连续区间和，这样就能获得一个子树对应的区间中的最大子段和。我就不做过多赘述了（懒）

总之是个练 splay 的好题啊，再次刷新我打 splay 的方法。

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct N{int f,s[2],d,sum,lm,rm,mx,rev,tag,sz;}e[500005];
int n,m,data[500005],cnt,root;
char opt[10];
stack<int> st;
int MKN()
{
    int tmp;
    if(st.empty())tmp=++cnt;
    else tmp=st.top(),st.pop();
    memset(&e[tmp],0,sizeof(N)),e[tmp].tag=1e8;
    return tmp;
}
bool pos(int a){return e[e[a].f].s[1]==a;}
void pup(int a)
{
    int l=e[a].s[0],r=e[a].s[1];
    e[a].sz=e[l].sz+e[r].sz+1;
    e[a].sum=e[l].sum+e[r].sum+e[a].d;
    e[a].mx=max(e[l].mx,e[r].mx);
    e[a].mx=max(e[a].mx,e[l].rm+e[a].d+e[r].lm);
    e[a].lm=max(e[l].lm,e[l].sum+e[a].d+e[r].lm);
    e[a].rm=max(e[r].rm,e[r].sum+e[a].d+e[l].rm);
}
void pdown(int a)
{
    int l=e[a].s[0],r=e[a].s[1];
    if(e[a].tag!=1e8)
    {
        if(l)e[l].tag=e[l].d=e[a].tag,e[l].sum=e[a].tag*e[l].sz;
        if(r)e[r].tag=e[r].d=e[a].tag,e[r].sum=e[a].tag*e[r].sz;
        if(e[a].tag>=0)
        {
            if(l)e[l].lm=e[l].rm=e[l].mx=e[l].sum;
            if(r)e[r].lm=e[r].rm=e[r].mx=e[r].sum;
        }
        else
        {
            if(l)e[l].lm=e[l].rm=0,e[l].mx=e[a].tag;
            if(r)e[r].lm=e[r].rm=0,e[r].mx=e[a].tag;
        }
        e[a].tag=1e8;
    }
    if(e[a].rev)
    {
        if(l)e[l].rev^=1,swap(e[l].lm,e[l].rm),swap(e[l].s[0],e[l].s[1]);
        if(r)e[r].rev^=1,swap(e[r].lm,e[r].rm),swap(e[r].s[0],e[r].s[1]);
        e[a].rev=0;
    }
}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}
int build(int l,int r,int fa)
{
    if(l>r)return 0;
    int mid=(l+r)>>1,a=MKN();
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a);
    e[a].f=fa,e[a].d=data[mid],pup(a);
    return a;
}
int find_by_order(int k)
{
    int a=root;
    while(a)
    {
        pdown(a);
        if(k<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            k-=e[e[a].s[0]].sz+1;
            if(!k)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void get_part(int&l,int&r,int pos,int tot)
{
    l=find_by_order(pos),r=find_by_order(pos+tot+1);
    splay(l,0),splay(r,l);
}
void work_insert()
{
    int pos,tot,l,r;
    IN(pos),IN(tot);
    for(int i=1;i<=tot;i++)IN(data[i]);
    get_part(l,r,pos+1,0);
    e[r].s[0]=build(1,tot,r),pup(r),pup(root);
}
void del_dfs(int a)
{
    if(!a)return;
    st.push(a),del_dfs(e[a].s[0]),del_dfs(e[a].s[1]);
}
void work_del()
{
    int pos,tot,l,r;
    IN(pos),IN(tot),get_part(l,r,pos,tot);
    del_dfs(e[r].s[0]),e[r].s[0]=0,pup(r),pup(root);
}
void work_update()
{
    int pos,tot,l,r,c,p;
    IN(pos),IN(tot),IN(c),get_part(l,r,pos,tot),p=e[r].s[0];
    if(p)
    {
        e[p].d=e[p].tag=c,e[p].sum=e[p].sz*c;
        if(c>=0)e[p].lm=e[p].rm=e[p].mx=e[p].sum;
        else e[p].lm=e[p].rm=0,e[p].mx=c;
    }
    pup(r),pup(root);
}
void work_rev()
{
    int pos,tot,l,r,p;
    IN(pos),IN(tot),get_part(l,r,pos,tot),p=e[r].s[0];
    if(p)e[p].rev^=1,swap(e[p].lm,e[p].rm),swap(e[p].s[0],e[p].s[1]);
}
void work_sum()
{
    int pos,tot,l,r;
    IN(pos),IN(tot),get_part(l,r,pos,tot);
    printf("%d\n",e[e[r].s[0]].sum);
}
void work_max()
{
    int l=find_by_order(1),r=find_by_order(e[root].sz);
    splay(l,0),splay(r,l),printf("%d\n",e[e[r].s[0]].mx);
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)IN(data[i+1]);
    e[0].mx=data[1]=-1e8,data[n+2]=1e8,root=build(1,n+2,0);
    while(m--)
    {
        scanf("%s",opt);
        if(opt[0]=='I')work_insert();
        else if(opt[0]=='D')work_del();
        else if(opt[0]=='M')
        {
            if(opt[2]=='K')work_update();
            else work_max();
        }
        else if(opt[0]=='R')work_rev();
        else work_sum();
    }
    return 0;
}