记录编号	455112	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]维护数列	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	3.282 s
提交时间	2017-10-01 13:07:14	内存使用	4.13 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define tp pair <Treap*,Treap*>
#define inf 0x3f3f3f3f
#define size(x) ((x!=NULL)?(x->size):(0))
#define maxl(x) ((x!=NULL)?(x->maxl):(0))
#define maxr(x) ((x!=NULL)?(x->maxr):(0))
#define maxn(x) ((x!=NULL)?(x->maxn):(-inf))
#define sum(x) ((x!=NULL)?(x->sum):(0))

struct Treap{
    Treap* ch[2];
    int key,val,size;
    int rev,lazy;
    int maxl,maxr,maxn,sum;
    Treap (int x){
        key=rand();val=x;size=1;
        rev=0; lazy=-inf;
        if(x>=0){maxl=maxr=maxn=sum=x;}
        else{maxl=maxr=0;maxn=sum=x;}
        ch[0]=ch[1]=NULL;
    }
    void change(int c){
        lazy=c;
        if(c>=0){
            val=c;
            maxl=maxr=maxn=sum=c*size;
        }
        else{
            maxl=maxr=0;
            maxn=val=c;sum=c*size;
        }
    }
    void rever(){
        rev^=1;
        swap(ch[0],ch[1]);
        swap(maxl,maxr);
    }
    void pushup(){
        size=size(ch[0])+size(ch[1])+1;
        sum=sum(ch[0])+sum(ch[1])+val;
        maxl=max(maxl(ch[0]),sum(ch[0])+val+maxl(ch[1]));
        maxr=max(maxr(ch[1]),sum(ch[1])+val+maxr(ch[0]));
        maxn=max(max(maxn(ch[0]),maxn(ch[1])),maxr(ch[0])+val+maxl(ch[1]));
    }
    void pushdown(){
        if(lazy!=-inf){
            if(ch[0])ch[0]->change(lazy);
            if(ch[1])ch[1]->change(lazy);
            lazy=-inf;rev=0;
        }
        if(rev){
            if(ch[0])ch[0]->rever();
            if(ch[1])ch[1]->rever();
            rev=0;
        }
    }
}*root;

inline void dfs(Treap *&o){
	if(!o) return ;
	dfs(o->ch[0]);
	dfs(o->ch[1]);
	delete o;
}
 
void print(Treap *x){
    if(x==NULL)return ;
    printf("key=%d  val=%d  size=%d  sum=%d  l=%d  r=%d  max=%d\n",x->key,x->val,x->size,x->sum,x->maxl,x->maxr,x->maxn);
    if(x->ch[0])print(x->ch[0]);
    if(x->ch[1])print(x->ch[1]);
}
 
 
Treap* merge(Treap* a,Treap* b){
    if(!a)return b;
    if(!b)return a;
    if(a->key <= b->key){
        a->pushdown();
        a->ch[1]=merge(a->ch[1],b);
        a->pushup(); return a;
    }
    else{
        b->pushdown();
        b->ch[0]=merge(a,b->ch[0]);
        b->pushup(); return b;
    }
}
tp split(Treap* a,int k){
    if(!a)return tp(NULL,NULL);
    a->pushdown();
    tp x;
    if(size(a->ch[0])>=k){
        x=split(a->ch[0],k);
        a->ch[0]=x.second;
        a->pushup();
        x.second=a;
    }
    else{
        x=split(a->ch[1],k-size(a->ch[0])-1);
        a->ch[1]=x.first;
        a->pushup();
        x.first=a;
    }
    return x;
}
 
int a[500050];
Treap* s[500050];
Treap* build(int tot){
    Treap *now,*last;
    int top=0;  
    for(int i=1;i<=tot;i++){
        now=new Treap (a[i]);
        last=NULL;
        while(top&&s[top]->key>now->key){
            s[top]->pushup();
            last=s[top--];
        }
        now->ch[0]=last;now->pushup();
        if(top){s[top]->ch[1]=now;s[top]->pushup();}
        s[++top]=now;
    }
    while(top) s[top--]->pushup();
    return s[1];
}
 
void work_insert(int pos,int tot){
    tp x=split(root,pos);
    root=merge(x.first,merge(build(tot),x.second));
}
void work_del(int pos,int tot){
    tp x=split(root,pos-1);
    tp y=split(x.second,tot);
    dfs(y.first);
    root=merge(x.first,y.second);
}
void work_change(int pos,int tot,int c){
    tp x=split(root,pos-1);
    tp y=split(x.second,tot);
    y.first->change(c);
    root=merge(x.first,merge(y.first,y.second));
}
void work_rev(int pos,int tot){
    tp x=split(root,pos-1);
    tp y=split(x.second,tot);
    y.first->rever();
    root=merge(x.first,merge(y.first,y.second));
}
void work_getsum(int pos,int tot){
    tp x=split(root,pos-1);
    tp y=split(x.second,tot);
    printf("%d\n",sum(y.first));
    root=merge(x.first,merge(y.first,y.second));
}
 
void work_maxsum(){printf("%d\n",root->maxn);}
 
 
int n,m;
int main(){
    freopen("seq2005.in","r",stdin);
    freopen("seq2005.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    root=build(n);
    char ss[20];
    int pos,tot,c;
    while(m--){
        scanf("%s",ss);
        if(ss[2]=='S'){//insert
            scanf("%d%d",&pos,&tot);
            for(int i=1;i<=tot;i++)scanf("%d",&a[i]);
            work_insert(pos,tot);
        }
        if(ss[2]=='L'){//del
            scanf("%d%d",&pos,&tot);
            work_del(pos,tot);
        }
        if(ss[2]=='K'){//change
            scanf("%d%d%d",&pos,&tot,&c);
            work_change(pos,tot,c);
        }
        if(ss[2]=='V'){//rev
            scanf("%d%d",&pos,&tot);
            work_rev(pos,tot);
        }
        if(ss[2]=='T'){//getsum
            scanf("%d%d",&pos,&tot);
            work_getsum(pos,tot);
        }
        if(ss[2]=='X'){
            work_maxsum();
        }
    }
    return 0;
}