记录编号	425192	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]维护数列	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	2.544 s
提交时间	2017-07-14 20:23:21	内存使用	3.60 MiB

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAXN 500005
using namespace std;
int lst[MAXN],n,m;


int read(){
    int x=0,f=1;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
    return x*f;
}

struct node{
    int r,v,s,filp,lmaxn,rmaxn,maxn,sum;
    bool tag;
    node *ch[2];

    void Maintain();

    node(){
        r=0;v=0;s=0;
        filp=0;sum=0;tag=0;
        maxn=lmaxn=rmaxn=-inf;
        ch[0]=ch[1]=NULL;
    }
    void push_down();

    node(int x);

    void* operator new(size_t);
    void operator delete (void* p);

}*null=new node(),*C,*mempool,*root;

typedef pair<node*,node*>pa;

vector<node*>bin;

void change_tag(node *p,int val){
    if(p==null)return;
    p->rmaxn=p->lmaxn=p->maxn=max(val,val*p->s);
    p->sum=val*p->s;
    p->v=val;
    p->tag=1;
}

void change_filp(node *p){
    if(p==null)return;
    p->filp^=1;
    swap(p->lmaxn,p->rmaxn);
}

node :: node(int x){
    v=x;r=rand();s=1;
    filp=tag=0;
    lmaxn=rmaxn=maxn=sum=v;
    ch[0]=ch[1]=null;
}

void node ::  push_down(){
    if(this==null)return;
    if(filp){
        filp^=1;
        change_filp(ch[0]);
        change_filp(ch[1]);
        swap(ch[0],ch[1]);
    }
    if(tag){
        change_tag(ch[0],v);
        change_tag(ch[1],v);
        tag=0;
    }
}

void node :: Maintain(){
    if(this==null)return;
    push_down();
    s=ch[0]->s+ch[1]->s+1;
    sum=ch[0]->sum+ch[1]->sum+v;
    maxn = max(max(ch[0]->rmaxn,0)+v+max(ch[1]->lmaxn,0),max(ch[0]->maxn,ch[1]->maxn));
    lmaxn = max(ch[0]->lmaxn,ch[0]->sum+v+max(ch[1]->lmaxn,0));
    rmaxn = max(ch[1]->rmaxn,ch[1]->sum+v+max(ch[0]->rmaxn,0));
}

void* node :: operator new(size_t){
    node *p;
    if(!bin.empty()){
        p=bin.back();
        bin.pop_back();
    }
    else{
        if(C==mempool){
            C = new node[1<<15];
            mempool = C+(1<<15);
        }
        p = C ++;
    }
    return p;
}

void node :: operator delete(void *p){
    bin.push_back((node*)p);
}

pa spilt(node *o,int k){
    o->push_down();
    if(!k)return make_pair(null,o);
    if(o==null)return make_pair(null,null);
    if(k<=o->ch[0]->s){
        pa y = spilt(o->ch[0],k);
        o->ch[0]=y.second;
        o->Maintain();
        y.second=o;
        return y;
    }
    else{
        pa y = spilt(o->ch[1],k-o->ch[0]->s-1);
        o->ch[1]=y.first;
        o->Maintain();
        y.first=o;
        return y;
    }
}

node* merge(node *a,node *b){
    a->push_down();b->push_down();
    if(a==null)return b;
    if(b==null)return a;
    if(a->r>b->r){
        a->ch[1]=merge(a->ch[1],b);
        a->Maintain();
        return a;
    }
    else{
        b->ch[0]=merge(a,b->ch[0]);
        b->Maintain();
        return b;
    }
}

int Rank(int x){
    node *o=root;
    int ans = 0;
    while(o!=null){
        if(x<=o->v)o=o->ch[0];
        else ans+=o->ch[0]->s+1,o=o->ch[1];
    }
    return ans;
}

void make_same(int pos,int tot){
    int w = read();
    pa o = spilt(root,pos-1);
    pa x = spilt(o.second,tot);
    change_tag(x.first,w);
    root = merge(o.first,merge(x.first,x.second));
}

void make_filp(int pos,int tot){
    if(tot==0)return;
    pa o = spilt(root,pos-1);
    pa x = spilt(o.second,tot);
    change_filp(x.first);
    node *tmp=merge(x.first,x.second);
    root = merge(o.first,tmp);
}

node *build(int l,int r){
    if(l>r)return null;
    int m = l+r>>1;
    node *p=new node(lst[m]);
    p->ch[0]=build(l,m-1);
    p->ch[1]=build(m+1,r);
    p->Maintain();
    return p;
}

void insert(int pos,int tot){
    for(int i=1;i<=tot;i++)scanf("%d",&lst[i]);
    pa x = spilt(root,pos);
    root = merge(merge(x.first,build(1,tot)),x.second);
}

void dfs(node *p){
    if(p==null)return;
    dfs(p->ch[0]);
    dfs(p->ch[1]);
    delete p;
}

void erase(int pos,int tot){
    pa x = spilt(root,pos-1);
    pa y = spilt(x.second,tot);
    dfs(y.first);
    root = merge(x.first,y.second);
}

inline int max_sum(){
    if(root==null)return 0;
    return root->maxn;
}

inline void sum(int pos,int tot){
    if(tot==0){printf("0\n");return;}
    pa x = spilt(root,pos-1);
    pa y = spilt(x.second,tot);
    printf("%d\n",y.first->sum);
    node *tmp = merge(y.first,y.second);
    root = merge(x.first,tmp);
}

void dfs1(node *p){
    if(p==null)return;
    dfs1(p->ch[0]);
    printf("%d ",p->v);
    dfs1(p->ch[1]);
}

int main(){
    freopen("seq2005.in","r",stdin);
    freopen("seq2005.out","w",stdout);
    root = null;
    n=read(),m=read();
    insert(0,n);
    while(m--){
        char opt[10];
        scanf("%s",opt);
        if(opt[0]=='M'){
            if(opt[2]=='X')printf("%d\n",max_sum());
            else{ 
                int pos = read(),tot = read();
                make_same(pos,tot);
            }
            continue;
        }
        int pos = read(),tot=read();
        if(opt[0]=='I')insert(pos,tot);
        if(opt[0]=='G')sum(pos,tot);
        if(opt[0]=='D')erase(pos,tot);
        if(opt[0]=='R')make_filp(pos,tot);
    }
}