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

#include<cstdio>
#include<cstring>
#include<algorithm>
#define dir(x) ((int)((x)==(x)->p->ch[1]))
using namespace std;
struct node{
	int data,size,sum,prefix,suffix,maxsum;
	bool rev,same;
	node *ch[2],*p;
	node(int d):data(d),size(1),sum(d),prefix(d),suffix(d),maxsum(d),rev(false),same(false){}
	void reverse(){
		if(data==-1000000)return;
		rev^=true;
		swap(prefix,suffix);
	}
	void makesame(int d){
		if(data==-1000000)return;
		data=d;
		sum=d*size;
		prefix=suffix=maxsum=max(sum,d);
		same=true;
	}
	void pushdown(){
		if(rev){
			ch[0]->reverse();
			ch[1]->reverse();
			swap(ch[0],ch[1]);
			rev=false;
		}
		if(same){
			ch[0]->makesame(data);
			ch[1]->makesame(data);
			same=false;
		}
	}
	void refresh(){
		size=ch[0]->size+ch[1]->size+1;
		sum=ch[0]->sum+ch[1]->sum+data;
		prefix=max(ch[0]->prefix,ch[0]->sum+data+max(ch[1]->prefix,0));
		suffix=max(ch[1]->suffix,ch[1]->sum+data+max(ch[0]->suffix,0));
		maxsum=max(max(ch[0]->maxsum,ch[1]->maxsum),max(ch[0]->suffix,0)+data+max(ch[1]->prefix,0));
	}
}*null=new node(-1000000),*root=null;
void insert(int,int);
void erase(int,int);
void makesame(int,int,int);
void reverse(int,int);
int getsum(int,int);
int maxsum();
node *build(int,int);
void removetree(node*);
node *kth(int);
void splay(node*,node*);
void rot(node*,int);
int n,m,pos,cnt,d,a[5000010];
char c[15];
int main(){
	freopen("seq2005.in","r",stdin);
	freopen("seq2005.out","w",stdout);
	null->ch[0]=null->ch[1]=null->p=null;
	null->size=null->sum=0;
	scanf("%d%d",&n,&m);
	insert(0,n);//dfs(root);
	while(m--){
		scanf("%s",c);
		if(!strcmp(c,"INSERT")){
			scanf("%d%d",&pos,&cnt);
			insert(pos,cnt);
		}
		else if(!strcmp(c,"DELETE")){
			scanf("%d%d",&pos,&cnt);
			erase(pos,cnt);
		}
		else if(!strcmp(c,"MAKE-SAME")){
			scanf("%d%d%d",&pos,&cnt,&d);
			makesame(pos,cnt,d);
		}
		else if(!strcmp(c,"REVERSE")){
			scanf("%d%d",&pos,&cnt);
			reverse(pos,cnt);
		}
		else if(!strcmp(c,"GET-SUM")){
			scanf("%d%d",&pos,&cnt);
			printf("%d\n",getsum(pos,cnt));
		}
		else if(!strcmp(c,"MAX-SUM"))printf("%d\n",maxsum());
	}
	return 0;
}
node *newnode(int d){
	node *x=new node(d);
	x->ch[0]=x->ch[1]=x->p=null;
	return x;
}
void insert(int pos,int cnt){
	for(int i=1;i<=cnt;i++)scanf("%d",&a[i]);
	node *x=build(1,cnt);
	if(root==null){
		root=x;
		return;
	}
	if(!pos){
		splay(kth(1),null);
		root->ch[0]=x;
		x->p=root;
		root->refresh();
	}
	else if(pos==root->size){
		splay(kth(root->size),null);
		root->ch[1]=x;
		x->p=root;
		root->refresh();
	}
	else{
		splay(kth(pos),null);
		splay(kth(pos+1),root);
		root->ch[1]->ch[0]=x;
		x->p=root->ch[1];
		root->ch[1]->refresh();
		root->refresh();
	}
}
void erase(int pos,int cnt){
	if(cnt==root->size){
		removetree(root);
		root=null;
		return;
	}
	if(pos==1){
		splay(kth(cnt+1),null);
		removetree(root->ch[0]);
		root->ch[0]=null;
		root->refresh();
	}
	else if(pos+cnt-1==root->size){
		splay(kth(pos-1),null);
		removetree(root->ch[1]);
		root->ch[1]=null;
		root->refresh();
	}
	else{
		splay(kth(pos-1),null);
		splay(kth(pos+cnt),root);
		removetree(root->ch[1]->ch[0]);
		root->ch[1]->ch[0]=null;
		root->ch[1]->refresh();
		root->refresh();
	}
}
void makesame(int pos,int cnt,int d){
	if(cnt==root->size)root->makesame(d);
	else if(pos==1){
		splay(kth(cnt+1),null);
		root->ch[0]->makesame(d);
		root->refresh();
	}
	else if(pos+cnt-1==root->size){
		splay(kth(pos-1),null);
		root->ch[1]->makesame(d);
		root->refresh();
	}
	else{
		splay(kth(pos-1),null);
		splay(kth(pos+cnt),root);
		root->ch[1]->ch[0]->makesame(d);
		root->ch[1]->refresh();
		root->refresh();
	}
}
void reverse(int pos,int cnt){
	if(cnt==root->size)root->reverse();
	else if(pos==1){
		splay(kth(cnt+1),null);
		root->ch[0]->reverse();
		root->refresh();
	}
	else if(pos+cnt-1==root->size){
		splay(kth(pos-1),null);
		root->ch[1]->reverse();
		root->refresh();
	}
	else{
		splay(kth(pos-1),null);
		splay(kth(pos+cnt),root);
		root->ch[1]->ch[0]->reverse();
		root->ch[1]->refresh();
		root->refresh();
	}
}
int getsum(int pos,int cnt){
	if(!cnt)return 0;
	if(cnt==root->size)return root->sum;
	else if(pos==1){
		splay(kth(cnt+1),null);
		return root->ch[0]->sum;
	}
	else if(pos+cnt-1==root->size){
		splay(kth(pos-1),null);
		return root->ch[1]->sum;
	}
	else{
		splay(kth(pos-1),null);
		splay(kth(pos+cnt),root);
		return root->ch[1]->ch[0]->sum;
	}
}
int maxsum(){
	if(root==null)return 0;
	root->pushdown();
	return root->maxsum;
}
node *build(int l,int r){
	if(l>r)return null;
	int mid=(l+r)>>1;
	node *x=newnode(a[mid]);
	if((x->ch[0]=build(l,mid-1))!=null)x->ch[0]->p=x;
	if((x->ch[1]=build(mid+1,r))!=null)x->ch[1]->p=x;
	x->refresh();
	return x;
}
void removetree(node *x){
	if(x==null)return;
	removetree(x->ch[0]);
	removetree(x->ch[1]);
	delete x;
}
node *kth(int k){
	node *rt=root;
	int d;
	while(rt){
		rt->pushdown();
		if(k==rt->ch[0]->size+1)return rt;
		if((d=k>rt->ch[0]->size))k-=rt->ch[0]->size+1;
		rt=rt->ch[d];
	}
	return null;
}
void splay(node *x,node *tar){
	while(x->p!=tar){
		if(x->p->p==tar){
			rot(x->p,dir(x)^1);
			break;
		}
		if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^1);
		else rot(x->p,dir(x)^1);
		rot(x->p,dir(x)^1);
	}
}
void rot(node *x,int d){
	node *y=x->ch[d^1];
	x->ch[d^1]=y->ch[d];
	if(y->ch[d]!=null)y->ch[d]->p=x;
	y->p=x->p;
	if(x->p!=null)x->p->ch[dir(x)]=y;
	else root=y;
	y->ch[d]=x;
	x->p=y;
	x->refresh();
	y->refresh();
}