记录编号 381620 评测结果 AAAAAAAAAA
题目名称 [NOI 2005]维护数列 最终得分 100
用户昵称 Gravatarwumingshi 是否通过 通过
代码语言 C++ 运行时间 1.380 s
提交时间 2017-03-12 10:08:29 内存使用 26.99 MiB
显示代码纯文本
#include<cstdio>
const int INF=2000;
inline int max(int a,int b){if(a>=b)return a;return b;}
inline int min(int a,int b){if(a<=b)return a;return b;}
inline void swap(int &a,int &b){a^=b;b^=a;a^=b;}
struct stack
{
	int t;
	int a[500010];
	inline void clear(){t=-1;}
	inline void push(int &n){a[++t]=n;}
	inline int top(){return a[t];}
	inline void pop(){t--;}
	inline bool empty(){return t<0;}
}reuse;
struct node
{
	int num,size,lmax,rmax,maxn,sum,id,rev;
	bool change;
	node *ch[2],*fa;
	inline void update()
	{
		size=ch[0]->size+ch[1]->size+1;
		sum=ch[0]->sum+ch[1]->sum;
		if(num!=-INF) sum+=num;
		lmax=max(ch[0]->lmax,max(ch[0]->sum+num,ch[0]->sum+ch[1]->lmax+num));
		rmax=max(ch[1]->rmax,max(ch[1]->sum+num,ch[1]->sum+ch[0]->rmax+num));
		maxn=max(ch[0]->maxn,ch[1]->maxn);
		maxn=max(maxn,max(ch[0]->rmax+num,ch[1]->lmax+num));
		maxn=max(maxn,max(ch[0]->rmax+ch[1]->lmax+num,num));
	}
	inline int getwh()
	{
		if(fa->ch[0]==this) return 0;return 1;
	}
	inline void pushchange(int n)
	{
		num=n;
		sum=size*n;
		maxn=lmax=rmax=max(num,sum);
		change=1;
	}
	inline void pushrev()
	{
		swap(lmax,rmax);
		node *tmp=ch[0];ch[0]=ch[1];ch[1]=tmp;
		rev^=1;
	}
	inline void setch(int wh,node *child);
	inline void pushdown();
}pool[500010],*root,*null,*newroot;
inline void node::setch(int wh,node *child)
{
	ch[wh]=child;
	if(child!=null) child->fa=this;
	update();
}
inline void node::pushdown()
{
	if(rev)
	{
		if(ch[0]!=null) ch[0]->pushrev();
		if(ch[1]!=null) ch[1]->pushrev();
		rev=0;
	}
	if(change)
	{
		if(ch[0]!=null) ch[0]->pushchange(num);
		if(ch[1]!=null) ch[1]->pushchange(num);
		change=0;
	}
}
char s[10];
int a[500010];
int n,m,tot,x,y,z;

inline void read(int &n)
{
	n=0;char c=getchar();bool b=0;
	while(c<'0'||c>'9'){if(c=='-')b=1;c=getchar();}
	while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();
	if(b) n*=-1;
}
inline void getstring()
{
	int p=-1;
	char c=getchar();
	while((c<'A'||c>'Z')&&c!='-') c=getchar();
	while((c>='A'&&c<='Z')||c=='-') s[++p]=c,c=getchar();
}
inline node *getnew(int num)
{
	node *now;
	if(!reuse.empty()) now=pool+reuse.top(),now->id=reuse.top(),reuse.pop();
	else now=pool+ ++tot,now->id=tot;
	now->ch[0]=now->ch[1]=now->fa=null;
	now->num=now->sum=now->maxn=now->lmax=now->rmax=num;
	if(num==-1e9) now->sum=0;
	now->size=1;
	now->change=now->rev=0;
	return now;
}
inline void rotate(node *now)
{
	node *fa=now->fa,*grand=now->fa->fa;
	int wh=now->getwh();
	fa->setch(wh,now->ch[wh^1]);
	now->setch(wh^1,fa);
	now->fa=grand;
	if(grand!=null)
	{
		if(grand->ch[0]==fa) grand->ch[0]=now;
		else grand->ch[1]=now;
	}
}
inline void splay(node *now,node *tar)
{
	for(;now->fa!=tar;rotate(now))
	  if(now->fa->fa!=tar)
	  {
		if(now->getwh()==now->fa->getwh()) rotate(now->fa);
		else rotate(now);
	  }
	if(tar==null) root=now;
}
node *build(int l,int r)
{
	int mid=(l+r)>>1;
	node *now=getnew(a[mid]);
	if(l<mid) now->setch(0,build(l,mid-1));
	if(r>mid) now->setch(1,build(mid+1,r));
	return now;
}
inline node *kth(int rank)
{
	node *now=root;
	int ranking=0;
	while(now!=null)
	{
		now->pushdown();
		int tmp=ranking+now->ch[0]->size;
		if(tmp+1==rank) return now;
		if(tmp+1>rank) now=now->ch[0];
		else ranking=tmp+1,now=now->ch[1];
	}
}
inline void insert(node *newone,int pos)
{
	splay(kth(pos),null);
	splay(kth(pos+1),root);
	root->ch[1]->setch(0,newone);
	root->update();
}
void dfs(node *now)
{
	reuse.push(now->id);
	if(now->ch[0]!=null) dfs(now->ch[0]);
	if(now->ch[1]!=null) dfs(now->ch[1]);
}
inline void del(int pos,int n)
{
	splay(kth(pos-1),null);
	splay(kth(pos+n),root);
	dfs(root->ch[1]->ch[0]);
	root->ch[1]->setch(0,null);
	root->update();
}
inline void changenum(int pos,int n,int num)
{
	splay(kth(pos-1),null);
	splay(kth(pos+n),root);
	root->ch[1]->ch[0]->pushchange(num);
	root->ch[1]->update();
	root->update();
}
inline void reverse(int pos,int n)
{
	splay(kth(pos-1),null);
	splay(kth(pos+n),root);
	root->ch[1]->ch[0]->pushrev();
	root->ch[1]->update();
	root->update();
}
inline int sum(int pos,int n)
{
	splay(kth(pos-1),null);
	splay(kth(pos+n),root);
	return root->ch[1]->ch[0]->sum;
}
int main()
{
	freopen("seq2005.in","r",stdin);
	freopen("seq2005.out","w",stdout);
	read(n),read(m);
	null=pool;
	null->ch[0]=null->ch[1]=null->fa=null;
	null->lmax=null->rmax=null->maxn=-INF;
	root=null;
	reuse.clear();
	for(register int i=1;i<=n;i++)
	  read(a[i]);
	a[0]=a[n+1]=-INF;
	root=build(0,n+1);
	while(m--)
	{
		getstring();
		if(s[0]=='I')
		{
			read(x),read(y);
			for(register int i=1;i<=y;i++)
			  read(a[i]);
			newroot=build(1,y);
			insert(newroot,x+1);
		}
		else if(s[0]=='D') read(x),read(y),del(x+1,y);
		else if(s[2]=='K') read(x),read(y),read(z),changenum(x+1,y,z);
		else if(s[0]=='R') read(x),read(y),reverse(x+1,y);
		else if(s[0]=='G') read(x),read(y),printf("%d\n",sum(x+1,y));
		else printf("%d\n",root->maxn);
	}
	return 0;
}