BZOJ 1500([NOI2005]检修数列-Splay的数列维护)

Description

Input

Output

Sample Input

Sample Output

HINT

Splay解决数列维护。

推荐：用伸展树解决数列维护问题

#include<cstdio>#include<cstring>#include<algorithm>#include<functional>#include<iostream>#include<cstdlib>#include<cmath>using namespace std;#define MAXN (500000+10)#define MAXM (20000+10)#define INF (0xfffffff)struct node{	int value,MaxL,MaxR,MaxM,sum,size;	bool rev,same;	node *ch[2],*pre;	node(node *f,int _value,int _MaxL,int _MaxR,int _MaxM,int _sum,int _size):value(_value),MaxL(_MaxL),MaxR(_MaxR),MaxM(_MaxM),sum(_sum),size(_size){rev=same=0,pre=f,ch[0]=ch[1]=NULL;}	node(){rev=same=0;}	int l_siz(){if (ch[0]) return ch[0]->size;else return 0;}//	int r_siz(){return (ch[1])?ch[1]->size:0;}		friend void pushdown(node *x)	{		if (x)		{			if (x->rev)			{				x->rev=0;				if (x->ch[0]) x->ch[0]->rev^=1;				if (x->ch[1]) x->ch[1]->rev^=1;				swap(x->ch[0],x->ch[1]);				swap(x->MaxL,x->MaxR);			}			if (x->same)			{				x->same=0;				if (x->ch[0]) {x->ch[0]->same=1;x->ch[0]->value=x->value;x->ch[0]->sum=x->value*x->ch[0]->size;x->ch[0]->MaxL=x->ch[0]->MaxR=x->ch[0]->MaxM=max(x->value,x->ch[0]->sum);}				if (x->ch[1]) {x->ch[1]->same=1;x->ch[1]->value=x->value;x->ch[1]->sum=x->value*x->ch[1]->size;x->ch[1]->MaxL=x->ch[1]->MaxR=x->ch[1]->MaxM=max(x->value,x->ch[1]->sum);}			}		}	}	friend void update(node *x)	{		if (x)		{			pushdown(x->ch[0]);pushdown(x->ch[1]); //由于有坑爹的rev操作，必须先down. 			x->size=((x->ch[0])?x->ch[0]->size:0)+((x->ch[1])?x->ch[1]->size:0)+1;			x->sum=((x->ch[0])?x->ch[0]->sum:0)+((x->ch[1])?x->ch[1]->sum:0)+x->value;			x->MaxL=max(((x->ch[0])?x->ch[0]->MaxL:x->value),((x->ch[0])?x->ch[0]->sum:0)+x->value+max(0,((x->ch[1])?x->ch[1]->MaxL:0)));			x->MaxR=max(((x->ch[1])?x->ch[1]->MaxR:x->value),((x->ch[1])?x->ch[1]->sum:0)+x->value+max(0,((x->ch[0])?x->ch[0]->MaxR:0)));		//	cout<<((x->ch[1])?x->ch[1]->MaxR:x->value)<<' '<<+max(0,(((x->ch[0])?x->ch[0]->MaxR:0)))<<endl;			x->MaxM=max(max(((x->ch[0])?x->ch[0]->MaxM:x->value),((x->ch[1])?x->ch[1]->MaxM:x->value)),((x->ch[0])?max(x->ch[0]->MaxR,0):0)+((x->ch[1])?max(x->ch[1]->MaxL,0):0)+x->value);		}	}};node *q[MAXN];int q_siz=0;int n,m,a[MAXN];node* newnode(node *f,int value,int MaxL,int MaxR,int MaxM,int sum,int size){	if (q_siz)	{		q[q_siz]->value=value;		q[q_siz]->MaxL=MaxL;		q[q_siz]->MaxR=MaxR;		q[q_siz]->MaxM=MaxM;		q[q_siz]->sum=sum;		q[q_siz]->size=size;		q[q_siz]->rev=q[q_siz]->same=0;q[q_siz]->pre=f;q[q_siz]->ch[0]=q[q_siz]->ch[1]=NULL;		return q[q_siz--];	}	node *x=new node(f,value,MaxL,MaxR,MaxM,sum,size);	return x;	}node* newnode(){	if (q_siz) return q[q_siz--];	node *x=new node();	return x;}void addnode(node *x){	q[++q_siz]=x;	*x=node();}struct Splay{	node *root;	Splay()	{		root=newnode(NULL,-INF,-INF,-INF,-INF,0,2);		root->ch[0]=newnode(root,-INF,-INF,-INF,-INF,0,1);	}	void Print(node *x)	{		if (x->ch[0]) {cout<<"(",Print(x->ch[0]),cout<<")-";}		cout<<x->same;		if (x->ch[1]) cout<<"-(",Print(x->ch[1]),cout<<")";	}	void rotate(node *x,int c) //0左旋 1右旋 	{		node *y=x->pre;		pushdown(y),pushdown(x);		y->ch[!c]=x->ch[c];		if (x->ch[c]!=NULL) x->ch[c]->pre=y;		x->pre=y->pre;		if (y->pre!=NULL)		{			if (y->pre->ch[0]==y) y->pre->ch[0]=x;			else y->pre->ch[1]=x;		}		x->ch[c]=y;y->pre=x;		if (y==root) root=x;		update(y);	}	void splay(node *x,node *f)	{		for(pushdown(x);x->pre!=f;)		{			if (x->pre->pre==f)			{				if (x->pre->ch[0]==x) rotate(x,1);				else rotate(x,0);			}			else			{				node *y=x->pre,*z=y->pre;				pushdown(z);pushdown(y);pushdown(x); //rev改变树结构 				if (y->ch[0]==x&&z->ch[0]==y) rotate(y,1),rotate(x,1);				else if (y->ch[1]==x&&z->ch[1]==y) rotate(y,0),rotate(x,0);				else if (y->ch[0]==x&&z->ch[1]==y) rotate(x,1),rotate(x,0);				else if (y->ch[1]==x&&z->ch[0]==y) rotate(x,0),rotate(x,1);			}				update(x);			//Print(root);cout<<endl;		}	} 	node* find_kth(node *x,int k)	{		pushdown(x); //确保x正确 		if (x->l_siz()>=k) return find_kth(x->ch[0],k);		if (x->l_siz()+1==k) return x;		else return find_kth(x->ch[1],k-x->l_siz()-1);	}	void build(node *f,node *x,int l,int r)	{		if (l>r) return;		int m=(l+r)>>1;		*x=node(f,a[m],a[l],a[r],a[m],a[m],1);		if (l<m) build(x,x->ch[0]=newnode(),l,m-1);		if (m<r) build(x,x->ch[1]=newnode(),m+1,r);		if (l<r) update(x);	}	void del(node *x)	{		if (x->ch[0]) del(x->ch[0]);		if (x->ch[1]) del(x->ch[1]);		addnode(x);	}	void insert(int pos,int tot)	{		splay(find_kth(root,pos+1),NULL);		splay(find_kth(root,pos+2),root);		root->ch[1]->ch[0]=newnode();		build(root->ch[1],root->ch[1]->ch[0],1,tot);		update(root->ch[1]);update(root);	}	void delet(int pos,int tot)	{		splay(find_kth(root,pos),NULL);		splay(find_kth(root,pos+1+tot),root);		//Print(root);		del(root->ch[1]->ch[0]);		root->ch[1]->ch[0]=NULL;		update(root->ch[1]);update(root);	}	void reverse(int pos,int tot)	{		splay(find_kth(root,pos),NULL);		splay(find_kth(root,pos+1+tot),root);		root->ch[1]->ch[0]->rev^=1;		update(root->ch[1]);update(root);	}	void make_same(int pos,int tot,int c)	{		splay(find_kth(root,pos),NULL);		splay(find_kth(root,pos+1+tot),root);		node *x=root->ch[1]->ch[0];		x->same=1;		x->value=c;		x->sum=c*x->size;		x->MaxL=x->MaxR=x->MaxM=max(x->value,x->sum);		update(root->ch[1]);update(root);	}	void get_sum(int pos,int tot)	{		if (tot==0)		{			printf("0\n");			return;		}		splay(find_kth(root,pos),NULL);		//Print(root);cout<<endl;		splay(find_kth(root,pos+1+tot),root);		//Print(root);cout<<endl;		node *x=root->ch[1]->ch[0];		printf("%d\n",x->sum);	}		void max_sum()	{		splay(find_kth(root,1),NULL);		splay(find_kth(root,root->size),root);		printf("%d\n",root->ch[1]->ch[0]->MaxM);	}}S;int main(){//	freopen("bzoj1500.in","r",stdin);	cin>>n>>m;	for (int i=1;i<=n;i++) cin>>a[i];	S.insert(0,n);	//S.Print(S.root);cout<<endl;	for (int i=1;i<=m;i++)	{	//	cout<<i<<':';		char s[10];		scanf("%s",s);		switch (s[2])		{			case'S':				{					int pos,tot;					scanf("%d%d",&pos,&tot);					for (int i=1;i<=tot;i++) scanf("%d",&a[i]);					S.insert(pos,tot);					break;				}			case'L':				{					int pos,tot;					scanf("%d%d",&pos,&tot);					S.delet(pos,tot);					break;				}			case'K':				{					int pos,tot,c;					scanf("%d%d%d",&pos,&tot,&c);					S.make_same(pos,tot,c);					break;				}			case'V':				{					int pos,tot;					scanf("%d%d",&pos,&tot);					S.reverse(pos,tot);					break;				}			case'T':				{					int pos,tot;					scanf("%d%d",&pos,&tot);					S.get_sum(pos,tot);					break;				}			case'X':				{					S.max_sum();					break;				}		}		//S.Print(S.root);cout<<endl;	}	return 0;}