BZOJ 1500 [NOI2005 D1T2] 维修数列

Description

Input

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

Output

对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

Sample Input

Sample Output

HINT

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

splay~

splay无敌组合版……做完这一道都要升华了……

符号很多，要注意区分~

#include<cstdio>#include<iostream>#include<queue>using namespace std;#define inf 999999999int n,m,a[500001],x,y,z,root,fa[500001],sum[500001],c[500001][2],id[500001],siz[500001],mx[500001],cnt,lx[500001],rx[500001],tag[500001],v[500001];bool rev[500001];char s[10];queue<int> q;int read(){	int totnum=0,f=1;char cc=getchar();	while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}	while(cc>='0' && cc<='9') {totnum=totnum*10+cc-'0';cc=getchar();}	return totnum*f;}void update(int u){	int l=c[u][0],r=c[u][1];	sum[u]=sum[l]+sum[r]+v[u];	siz[u]=siz[l]+siz[r]+1;	mx[u]=max(mx[l],mx[r]);	mx[u]=max(mx[u],rx[l]+v[u]+lx[r]);	lx[u]=max(lx[l],v[u]+sum[l]+lx[r]);	rx[u]=max(rx[r],v[u]+sum[r]+rx[l]);}void pushdown(int u){	int l=c[u][0],r=c[u][1];	if(tag[u])	{		rev[u]=tag[u]=0;		if(l) tag[l]=1,v[l]=v[u],sum[l]=v[u]*siz[l];		if(r) tag[r]=1,v[r]=v[u],sum[r]=v[u]*siz[r];		if(v[u]>=0)		{			if(l) lx[l]=rx[l]=mx[l]=sum[l];			if(r) lx[r]=rx[r]=mx[r]=sum[r];		}		else		{			if(l) lx[l]=rx[l]=0,mx[l]=v[u];			if(r) lx[r]=rx[r]=0,mx[r]=v[u];		}	}	if(rev[u])	{		rev[u]=0;rev[l]^=1;rev[r]^=1;		swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);		swap(lx[l],rx[l]);swap(lx[r],rx[r]);	}}void build(int l,int r,int k){	if(l>r) return;	int la=id[k],mid=(l+r)>>1,now=id[mid];	if(l==r)	{		tag[now]=rev[now]=0;mx[now]=sum[now]=a[l];siz[now]=1;		if(a[l]>=0) lx[now]=rx[now]=a[l];		else lx[now]=rx[now]=0;	}	else build(l,mid-1,mid),build(mid+1,r,mid);	v[now]=a[mid];fa[now]=la;update(now);	c[la][mid>=k]=now;}void rotate(int x,int &k){	int y=fa[x],z=fa[y],l,r;	if(c[y][0]==x) l=0;	else l=1;r=l^1;	if(y==k) k=x;	else if(c[z][0]==y) c[z][0]=x;	else c[z][1]=x;	fa[x]=z;fa[y]=x;fa[c[x][r]]=y;	c[y][l]=c[x][r];c[x][r]=y;	update(y);update(x);}void splay(int x,int &k){	while(x!=k)	{		int y=fa[x],z=fa[y];		if(y!=k)		{			if(c[z][0]==y ^ c[y][0]==x) rotate(x,k);			else rotate(y,k);		}		rotate(x,k);	}}int findd(int u,int k){	int l=c[u][0],r=c[u][1];	if(rev[u] || tag[u]) pushdown(u);	if(siz[l]+1==k) return u;	if(siz[l]>=k) return findd(l,k);	return findd(r,k-siz[l]-1);}int kk(int l,int r){	int x=findd(root,l),y=findd(root,l+r+1);	splay(x,root);splay(y,c[x][1]);	return c[y][0];}void add(int u,int tot){	for(int i=1;i<=tot;i++) a[i]=read();	for(int i=1;i<=tot;i++)	  if(!q.empty()) id[i]=q.front(),q.pop();	  else id[i]=++cnt;	build(1,tot,0);	int x=findd(root,u+1),y=findd(root,u+2),z=id[(1+tot)>>1];	splay(x,root);splay(y,c[x][1]);	fa[z]=y;c[y][0]=z;	update(y);update(x);}void rec(int u){	if(!u) return;	int l=c[u][0],r=c[u][1];	rec(l);rec(r);q.push(u);	fa[u]=c[u][0]=c[u][1]=rev[u]=tag[u]=0;}void del(int u,int tot){	int x=kk(u,tot),y=fa[x];	rec(x);c[y][0]=0;	update(y);update(fa[y]);}void chan(int u,int tot,int val){	int x=kk(u,tot),y=fa[x];	v[x]=val;tag[x]=1;sum[x]=v[x]*siz[x];	if(val>=0) lx[x]=rx[x]=mx[x]=sum[x];	else lx[x]=rx[x]=0,mx[x]=val;	update(y);update(fa[y]);}void rever(int u,int tot){	int x=kk(u,tot),y=fa[x];	if(!tag[x])	{		rev[x]^=1;		swap(c[x][0],c[x][1]);		swap(lx[x],rx[x]);		update(y);update(fa[y]);	}}int main(){	n=read();m=read();a[1]=a[n+2]=mx[0]=-inf;	for(int i=1;i<=n;i++) a[i+1]=read();	for(int i=1;i<=n+2;i++) id[i]=i;cnt=n+2;	build(1,n+2,0);root=(n+3)>>1;	int pos,tot,val;	while(m--)	{		scanf("%s",s);		switch(s[2])		{			case('S'):pos=read();tot=read();add(pos,tot);break;			case('L'):pos=read();tot=read();del(pos,tot);break;			case('K'):pos=read();tot=read();val=read();chan(pos,tot,val);break;			case('V'):pos=read();tot=read();rever(pos,tot);break;			case('T'):pos=read();tot=read();PRintf("%d/n",sum[kk(pos,tot)]);break;			case('X'):printf("%d/n",mx[root]);break;		}	}	return 0;}