记录编号	245479	评测结果	ATTTTTTWWW
题目名称	[NOI 2005]维护数列	最终得分	10
用户昵称	TenderRun	是否通过	未通过
代码语言	C++	运行时间	20.747 s
提交时间	2016-04-03 13:40:57	内存使用	189.11 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=5000010;
const int INF=547483647;
int fa[maxn],ch[maxn][2],sz[maxn],key[maxn];
int mark[maxn],flip[maxn],sum[maxn],n,Q;
int lx[maxn],rx[maxn],mx[maxn],rt,cnt;
 
void Push_up(int x){
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];
	lx[x]=max(lx[ch[x][0]],key[x]+sum[ch[x][0]]+lx[ch[x][1]]);
	rx[x]=max(rx[ch[x][1]],key[x]+sum[ch[x][1]]+rx[ch[x][0]]);
	mx[x]=max(max(mx[ch[x][0]],mx[ch[x][1]]),key[x]+rx[ch[x][0]]+lx[ch[x][1]]);
}
 
void Cover(int x,int d){
	if(!x)return;
	key[x]=mark[x]=d;
	sum[x]=sz[x]*d;
	if(d>0)lx[x]=rx[x]=mx[x]=sum[x];
	else lx[x]=rx[x]=0,mx[x]=d;
}
 
void Flip(int x){
	if(!x)return;
	swap(ch[x][0],ch[x][1]);
	swap(lx[x],rx[x]);flip[x]^=1;
}
 
void Push_down(int x){
	if(mark[x]!=INF){
		Cover(ch[x][0],mark[x]);
		Cover(ch[x][1],mark[x]);
		mark[x]=INF;
	}
	if(flip[x]){
		Flip(ch[x][0]);
		Flip(ch[x][1]);
		flip[x]=0;
	}
}
 
void Rotate(int x){
	int y=fa[x],g=fa[y],c=ch[y][1]==x;
	ch[y][c]=ch[x][c^1];fa[ch[y][c]]=y;
	ch[x][c^1]=y;fa[y]=x;fa[x]=g;
	if(g)ch[g][ch[g][1]==y]=x;
	Push_up(y);
}
 
void Splay(int x,int g=0){
	for(int y;(y=fa[x])!=g;Rotate(x))
		if(fa[y]!=g)
			Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
	if(!g)rt=x;
	Push_up(x);		
}
 
void Rtr(int k,int g=0){
	int p=rt;
	while(true){
		Push_down(p);
		if(sz[ch[p][0]]+1==k)break;
		if(sz[ch[p][0]]+1<k){
			k-=sz[ch[p][0]]+1;
			p=ch[p][1];
		}
		else
			p=ch[p][0];
	}
	Splay(p,g);
}
 
int Build(int x,int l,int r){
	int mid=(l+r)>>1;
	if(l<=mid-1)ch[mid][0]=Build(mid,l,mid-1);
	fa[mid]=x;sz[mid]=1;
	if(mid!=1&&mid!=n)
		scanf("%d",&key[mid]);
	else
		key[mid]=-INF;		
	mark[mid]=INF;	
	if(mid+1<=r)ch[mid][1]=Build(mid,mid+1,r);
	Push_up(mid);
	return mid;
}
 
int Insert(int x,int l,int r){
	int mid=(l+r)>>1,p=++cnt;
	fa[p]=x;sz[p]=1;mark[p]=INF;
	if(l<mid)ch[p][0]=Insert(p,l,mid-1);
	scanf("%d",&key[p]);
	if(r>mid)ch[p][1]=Insert(p,mid+1,r);
	Push_up(p);	
	return p;
}
char s[15];
 
void Debug(int x){
	if(!x)return;
	Push_down(x);
	Debug(ch[x][0]);
	//printf("%d ",key[x]);
	Debug(ch[x][1]);
}
 
int main(){
	freopen("seq2005.in","r",stdin);
	freopen("seq2005.out","w",stdout);
	scanf("%d%d",&n,&Q);n+=2;
	rt=Build(0,1,n);cnt=n;
	int l,r,x,d;
	while(Q--){
		scanf("%s",s);
		if(!strcmp(s,"MAX-SUM")){
			Rtr(1);Rtr(n,rt);
			printf("%d\n",mx[rt]);
		}
		else if(!strcmp(s,"INSERT")){
			scanf("%d%d",&l,&x);l+=1;
			Rtr(l);Rtr(l+1,rt);
			Push_down(rt);
			Push_down(ch[rt][1]);
			ch[ch[rt][1]][0]=Insert(ch[rt][1],1,x);
		}
		else if(!strcmp(s,"DELETE")){
			scanf("%d%d",&l,&x);r=l+x+1;
			Rtr(l);Rtr(r,rt);
			ch[ch[rt][1]][0]=0;
			Push_up(ch[rt][1]);
			Push_up(rt);
		}
		else if(!strcmp(s,"REVERSE")){
			scanf("%d%d",&l,&x);r=l+x+1;
			Rtr(l);Rtr(r,rt);
			Flip(ch[ch[rt][1]][0]);
		}
		else if(!strcmp(s,"MAKE-SAME")){
			scanf("%d%d%d",&l,&x,&d);r=l+x+1;
			Rtr(l);Rtr(r,rt);
			Cover(ch[ch[rt][1]][0],d);
			Push_up(ch[rt][1]);
			Push_up(rt);
		}
		else if(!strcmp(s,"GET-SUM")){
			scanf("%d%d",&l,&x);r=l+x+1;
			Rtr(l);Rtr(r,rt);
			Push_down(rt);
			Push_down(ch[rt][1]);
			printf("%d\n",sum[ch[ch[rt][1]][0]]);
		}
		//printf("<");
		//Debug(rt);
		//printf(">\n");
	}
	return 0;
}