记录编号	257628	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]维护数列	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	4.610 s
提交时间	2016-05-02 14:47:54	内存使用	28.93 MiB

#include<cstdio>
#include<iostream>
using namespace std;
#define LL(x) (ch[x][0])
#define RR(x) (ch[x][1])
#define Kt (ch[ ch[rt][1] ][0])
const int INF = 0x7fffffff ;
const int maxn = 500000 + 100;
int a[maxn];
struct SplayTree{
	int rt,top1,top2;
	int pre[maxn],sz[maxn],ch[maxn][2],stk[maxn],que[maxn];
	//  前驱      节点大小  左右儿子      栈       队列 
	int same[maxn],flag[maxn],valu[maxn];
	int flip[maxn],sum[maxn],lmx[maxn],rmx[maxn],mx[maxn];//辅助数组 

	void addNode(int pos,int &x,int f){//添加新节点 
		if(top2) x=stk[--top2];
		else x=++top1;

		LL(x)=RR(x)=0; pre[x]=f;
		flag[x]=flip[x]=0;
		valu[x]=a[pos];
		sum[x]=lmx[x]=rmx[x]=mx[x]=-INF;
	}
	inline void iswap(int x){
		if(x==0)return;
		flip[x]^=1;
		swap(LL(x),RR(x));
		swap(lmx[x],rmx[x]);
	}
	inline void toSame(int x,int c){
		if(x==0) return;
		flag[x]=1,same[x]=c;
		valu[x]=c,sum[x]=sz[x]*c;
		lmx[x]=rmx[x]=mx[x]=max(sum[x],valu[x]);
	}
	void PushDown(int x){
		if(x==0) return;
		if(flip[x]){
			iswap(LL(x)); iswap(RR(x));
			flip[x]=0;
		}
		if(flag[x]){
			toSame(LL(x),same[x]);
			toSame(RR(x),same[x]);
			flag[x]=0;
		}
	}
	void PushUp(int x){//节点信息更新 
		sz[x]=1+sz[LL(x)]+sz[RR(x)];

		sum[x]=valu[x]+sum[LL(x)]+sum[RR(x)];
		mx[x]=lmx[x]=rmx[x]=-INF;

		lmx[x]=max(lmx[LL(x)],sum[LL(x)]+valu[x]+max(0,lmx[RR(x)]));
		rmx[x]=max(rmx[RR(x)],sum[RR(x)]+valu[x]+max(0,rmx[LL(x)]));

		mx[x]=max(mx[LL(x)],mx[RR(x)]);
		mx[x]=max(mx[x],valu[x]+max(0,rmx[LL(x)])+max(0,lmx[RR(x)]));
	}
	inline void Link(int x,int y,int f){//Link不用解释了吧 
		pre[x]=y; ch[y][f]=x;
	}
	inline void Rotate(int x,int f){//0表示左旋，1表示右旋
		int y=pre[x],z=pre[y];

		PushDown(y); PushDown(x);

		Link(ch[x][f],y,!f);
		Link(x,z,RR(z)==y);
		Link(y,x,f);

		PushUp(y);
	}
	inline void Splay(int x,int goal){//将节点x旋转到goal下面
		while(pre[x]!=goal){
			int y=pre[x],z=pre[y];
			int cx=(LL(y)==x),cy=(LL(z)==y);

			if(z==goal) Rotate(x,cx);
			else{
				if(cx==cy) Rotate(y,cy);
				else Rotate(x,cx);
				Rotate(x,cy);
			}
		}
		PushUp(x);
		if(goal==0) rt=x;
	}
	inline void Select(int K,int goal){//将第K个数旋转到goal下面。
		int x=rt;
		PushDown(x);
		while(sz[LL(x)]!=K){
			if(K<sz[LL(x)]) x=ch[x][0];
			else K-=sz[LL(x)]+1,x=ch[x][1];
			PushDown(x);
		}
		Splay(x,goal);
	}
	void Erase(int x){//删除以x为根的子树
		int father=pre[x];
		int head=0,tail=0;
		for(que[tail++]=x;head<tail;head++){
			stk[top2++]=que[head];
			if(LL(que[head])) que[tail++]=LL(que[head]);
			if(RR(que[head])) que[tail++]=RR(que[head]);
		}
		ch[father][ RR(father)==x ]=0;
	}
	void Insert(){//插入一段区间
		int pos,tot;
		scanf("%d%d",&pos,&tot);

		for(int i=1;i<=tot;i++) scanf("%d",&a[i]);

		Select(pos,0), Select(pos+1,rt);
		build(1,tot,Kt,ch[rt][1]);
		Splay(ch[rt][1],0);
	}
	void Delete(){//删除一段区间
		int pos,tot;
		scanf("%d%d",&pos,&tot);

		Select(pos-1,0), Select(pos+tot,rt);

		Erase(Kt);

		Splay(ch[rt][1],0);
	}
	void MakeSame(){//将一段区间内的值全部变成C
		int pos,tot,c;
		scanf("%d%d%d",&pos,&tot,&c);

		Select(pos-1,0), Select(pos+tot,rt);

		toSame(Kt,c);
		Splay(ch[rt][1],0);
	}
	void Reverse(){//将一段区间进行旋转
		int pos,tot;
		scanf("%d%d",&pos,&tot);

		Select(pos-1,0), Select(pos+tot,rt);
		iswap(Kt);
		Splay(ch[rt][1],0);
	}
	void GetSum(){//求一段区间和
	
		int pos,tot;
		scanf("%d%d",&pos,&tot);

		Select(pos-1,0), Select(pos+tot,rt);

		printf("%d\n",sum[Kt]);
	}
	void MaxSum(){//求出子区间和的最大值。
	
		Splay(1,0);
		Splay(2,1);
		printf("%d\n",mx[Kt]);
	}
	void build(int l,int r,int &x,int f){//建树
	
		if(l>r) return;

		int mid=l+r >> 1;
		addNode(mid,x,f);
		build(l,mid-1,LL(x),x);
		build(mid+1,r,RR(x),x);
		PushUp(x);
	}

	void init(int st,int ed){//初始化
	
		rt=top1=top2=0;
		sz[0]=pre[0]=LL(0)=RR(0)=0;

		lmx[0]=rmx[0]=mx[0]=-INF;

		addNode(0,rt,0); addNode(0,RR(rt),rt);

		build(st,ed,Kt,RR(rt));
		PushUp(RR(rt)); PushUp(rt);
	}
}Sky_miner;
int main(){
	freopen("seq2005.in","r",stdin);
	freopen("seq2005.out","w",stdout);
	int n,m;scanf("%d%d",&n,&m);
	a[0] = -INF;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	Sky_miner.init(1,n);
	char buf[100];
	for(int i=0;i<m;i++){
		scanf("%s",buf);
		if(buf[0]=='I') Sky_miner.Insert();
		else if(buf[0]=='D') Sky_miner.Delete();
		else if(buf[0]=='M'){
			if(buf[2]=='K') Sky_miner.MakeSame();
			else Sky_miner.MaxSum();
		}
		else if(buf[0]=='R') Sky_miner.Reverse();
		else Sky_miner.GetSum();
	}
	return 0;
}