题目描述

Description

Input

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

Output

对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

Sample Input

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

Sample Output

-1
10
1
10

HINT

题目分析

splay的题不用非旋treap写 那还是人么= =
这里保证了标记只对自己的儿子的儿子有效 至于自己的儿子 在打标记时就已经更新完了
学了一发O(n)建树 单调栈建树和递归建树
这里就只贴递归建树了 好些好用
还有这题卡内存 所以我们用一个队列来循环利用 不用的数组下标

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
int size[601010],lson[601010],rson[601010],key[601010],val[601010];
int root,tot;
int sum[601010],lmax[601010],rmax[601010],maxx[601010];
int lazy[601010],add[601010];
queue<int> q;
void update(int x)
{
    size[x]=size[lson[x]]+size[rson[x]]+1;
    sum[x]=sum[lson[x]]+sum[rson[x]]+val[x];
    lmax[x]=rmax[x]=0,maxx[x]=-0x3f3f3f3f;
    if(lson[x]) lmax[x]=max(lmax[x],lmax[lson[x]]);
    lmax[x]=max(lmax[x],sum[lson[x]]+val[x]+lmax[rson[x]]);
    if(rson[x]) rmax[x]=max(rmax[x],rmax[rson[x]]);
    rmax[x]=max(rmax[x],sum[rson[x]]+val[x]+rmax[lson[x]]);
    if(lson[x]) maxx[x]=max(maxx[x],maxx[lson[x]]);
    if(rson[x]) maxx[x]=max(maxx[x],maxx[rson[x]]);
    maxx[x]=max(maxx[x],rmax[lson[x]]+val[x]+lmax[rson[x]]);
    return ;
}
void rev(int x)
{
    swap(lmax[x],rmax[x]);
    swap(lson[x],rson[x]);
    lazy[x]^=1;
}
void ad(int x,int c)
{
    sum[x]=size[x]*c;
    if(c>0) lmax[x]=rmax[x]=maxx[x]=size[x]*c;
    else lmax[x]=rmax[x]=0,maxx[x]=c;
    val[x]=add[x]=c;
    return ;
}
void pushdown(int x)
{
    if(!x) return ;
    if(add[x]!=0x3f3f3f3f)
    {
        if(lson[x]) sum[lson[x]]=size[lson[x]]*add[x],val[lson[x]]=add[lson[x]]=add[x];
        if(rson[x]) sum[rson[x]]=size[rson[x]]*add[x],val[rson[x]]=add[rson[x]]=add[x];
        if(add[x]>0)
        {
            if(lson[x]) lmax[lson[x]]=rmax[lson[x]]=maxx[lson[x]]=size[lson[x]]*add[x];
            if(rson[x]) lmax[rson[x]]=rmax[rson[x]]=maxx[rson[x]]=size[rson[x]]*add[x];
        }
        else
        {
            if(lson[x]) lmax[lson[x]]=rmax[lson[x]]=0,maxx[lson[x]]=add[x];
            if(rson[x]) lmax[rson[x]]=rmax[rson[x]]=0,maxx[rson[x]]=add[x];
        }
        add[x]=0x3f3f3f3f;
    }
    if(lazy[x]) 
    {
        swap(lson[lson[x]],rson[lson[x]]);
        swap(lson[rson[x]],rson[rson[x]]);
        swap(lmax[lson[x]],rmax[lson[x]]);
        swap(lmax[rson[x]],rmax[rson[x]]);
        if(lson[x]) lazy[lson[x]]^=1;
        if(rson[x]) lazy[rson[x]]^=1;
        lazy[x]=0;
    }
    return ;
}
int merge(int x,int y)
{
    pushdown(x),pushdown(y);
    if(x==0||y==0) return x|y;
    if(key[x]<key[y])
    {
        lson[y]=merge(x,lson[y]),update(y);
        return y;
    }
    rson[x]=merge(rson[x],y),update(x);
    return x;
}
par split(int x,int k)
{
    if(k==0) return make_pair(0,x);
    pushdown(x);
    int l=lson[x],r=rson[x];
    if(k==size[lson[x]])
    {
        lson[x]=0,update(x);
        return make_pair(l,x);
    }
    if(k==size[lson[x]]+1)
    {
        rson[x]=0,update(x);
        return make_pair(x,r);
    }
    par t;
    if(k<size[lson[x]])
    {
        t=split(l,k);
        lson[x]=t.second,update(x);
        return make_pair(t.first,x);
    }
    else
    {
        t=split(r,k-size[lson[x]]-1);
        rson[x]=t.first,update(x);
        return make_pair(x,t.second);
    }
}
int num[600100],sta[600100];
char s[100];
void newnode(int x,int c)
{
    val[x]=c,size[x]=1,key[x]=rand();
    lmax[x]=rmax[x]=max(c,0),maxx[x]=sum[x]=c;
    add[x]=0x3f3f3f3f;
    return ;
}
int build(int l,int r)
{
    if(l==r) 
    {
        int nmp=q.front();
        q.pop();
        newnode(nmp,num[l]);
        return nmp;
    }
    int mid=(l+r)>>1;
    return merge(build(l,mid),build(mid+1,r));
}
void insert(int x,int y)
{
    for(int i=1;i<=y;i++) scanf("%d",&num[i]);
    par t1=split(root,x);
    root=merge(merge(t1.first,build(1,y)),t1.second);
}
void dfs(int x)
{
    if(!x) return ;
    int l=lson[x],r=rson[x];
    size[x]=lmax[x]=rmax[x]=maxx[x]=sum[x]=val[x]=0;
    lazy[x]=0,add[x]=0x3f3f3f3f,lson[x]=rson[x]=0;
    dfs(l),q.push(x),dfs(r);
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int x,i=1;i<=n;i++)
        scanf("%d",&x),newnode(++tot,x),root=merge(root,tot);
    for(int i=n+1;i<=501010;i++) q.push(i);
    for(int x,y,c,i=1;i<=m;i++)
    {
        scanf("%s",&s[0]);
        if(s[2]=='S') scanf("%d%d",&x,&y),insert(x,y);   
        else if(s[2]=='L')
        {
            scanf("%d%d",&x,&y);
            par t1,t2;
            t2=split(root,x+y-1),t1=split(t2.first,x-1);
            dfs(t1.second);
            root=merge(t1.first,t2.second);
        }
        else if(s[2]=='K')
        {
            scanf("%d%d%d",&x,&y,&c);
            par t1,t2;
            t2=split(root,x+y-1),t1=split(t2.first,x-1);
            ad(t1.second,c);
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(s[2]=='V')
        {
            scanf("%d%d",&x,&y);
            par t1,t2;
            t2=split(root,x+y-1),t1=split(t2.first,x-1);
            rev(t1.second);
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(s[2]=='T')
        {
            scanf("%d%d",&x,&y);
            par t1,t2;
            t2=split(root,x+y-1),t1=split(t2.first,x-1);
            printf("%d\n",sum[t1.second]);
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(s[2]=='X') printf("%d\n",maxx[root]);
    }   
    return 0;
}