wy's Blog

1500: [NOI2005]维修数列

Description

Input

Output

Sample Input

Sample Output

HINT

Splay

这还是一道提高代码能力的好题。。。

#include<cstdio>
#include<iostream>
using namespace std;
int N,M,root,num;
int A[500010];
int stack[500010],t;
struct point{
	int fa,d,key,sum,size,rev,same;
	int maxsum,rmax,lmax;
	int son[2];
}P[500010];
void New(int u,int fa,int d,int key){
	P[u].fa=fa;
	P[u].key=key;
	P[u].d=d;
	P[u].sum=key;
	P[u].son[0]=P[u].son[1]=0;
	P[u].size=1;
	P[u].maxsum=key;
	P[u].rev=P[u].same=0;
	P[u].rmax=P[u].lmax=key;
}
void Up(int u){
	int l=P[u].son[0],r=P[u].son[1];
	P[u].sum=P[l].sum+P[r].sum+P[u].key;
	P[u].size=P[l].size+P[r].size+1;
	P[u].maxsum=max(P[l].rmax,0)+P[u].key+max(P[r].lmax,0);
	P[u].maxsum=max(P[u].maxsum,max(P[l].maxsum,P[r].maxsum));
	P[u].lmax=max(P[l].lmax,P[l].sum+P[u].key+max(P[r].lmax,0));
	P[u].rmax=max(P[r].rmax,P[r].sum+P[u].key+max(P[l].rmax,0));
}
void Same(int u,int v){
	if (!u) return;
	P[u].key=v;
	P[u].sum=v*P[u].size;
	P[u].lmax=P[u].rmax=P[u].maxsum=max(v,P[u].sum);
	P[u].same=1;
}
void Rev(int u){
	if (!u) return;
	swap(P[u].son[0],P[u].son[1]);
	P[P[u].son[0]].d=0;
	P[P[u].son[1]].d=1;
	swap(P[u].lmax,P[u].rmax);
	P[u].rev^=1;
}
void Down(int u){
	if (!u) return;
	if (P[u].same){
		Same(P[u].son[0],P[u].key);
		Same(P[u].son[1],P[u].key);
		P[u].same=0;
	}
	if (P[u].rev){
		Rev(P[u].son[0]);
		Rev(P[u].son[1]);
	    P[u].rev=0;
	}
}
void Turn(int x){
    int y=P[x].fa; int z=P[y].fa;
	int dx=P[x].d; int dy=P[y].d;
	P[x].fa=z; P[x].d=dy;
	if (dy<2) P[z].son[dy]=x;
	dy=1-dx; z=P[x].son[dy];
	P[y].fa=x; P[y].d=dy; P[x].son[dy]=y;
	P[z].fa=y; P[z].d=dx; P[y].son[dx]=z;
	Up(y);
	Up(x);
}
void Add(int &u,int l,int r,int fa,int d){
	if (l>r) return;
	int mid=(l+r)/2;
	if (t) u=stack[t--];
	else u=++num;
	New(u,fa,d,A[mid]);
	Add(P[u].son[0],l,mid-1,u,0);
	Add(P[u].son[1],mid+1,r,u,1);
	Up(u);
}
void Build(){
	root=num=1;
	P[0].fa=P[0].d=P[0].key=P[0].sum=P[0].size=0;
	P[0].rev=P[0].same=0;
	P[0].maxsum=P[0].rmax=P[0].lmax=-1e7;
	New(root,0,2,0);
	for (int i=0;i<N;++i)
	    scanf("%d",&A[i]);
	Add(P[root].son[1],0,N,root,1);
	Up(root);
}
void Splay(int u,int x){
	for (;P[u].fa!=x;){
		Down(P[P[u].fa].fa); Down(P[u].fa); Down(u);
		if (P[P[u].fa].fa!=x)
		    if (P[u].d==P[P[u].fa].d)
		        Turn(P[u].fa);
		    else Turn(u);
	    if (P[u].fa==x) break;
	    Turn(u);
	}
	Up(u);
	if (!x) root=u;
}
int find(int k){
	int s=0;
	int u=root;
	for (;;){
		Down(u);
		if (s+P[P[u].son[0]].size+1==k) return u;
		if (s+P[P[u].son[0]].size+1>k)
		    u=P[u].son[0];
		else {
			s+=(P[P[u].son[0]].size+1);
			u=P[u].son[1];
		}
	}
}
void Insert(int pos,int tot){
	for (int i=1;i<=tot;++i)
	    scanf("%d",&A[i]);
	int u1=find(pos+1);
	int u2=find(pos+2);
	Splay(u1,0);
	Splay(u2,u1);
	Add(P[u2].son[0],1,tot,u2,0);
    Up(u2);
    Up(u1);
}
void Clear(int u){
	if (!u) return;
	stack[++t]=u;
	Clear(P[u].son[0]);
	Clear(P[u].son[1]);
}
void Delete(int pos,int tot){
    int u1=find(pos);
	int u2=find(pos+tot+1);
	Splay(u1,0);
	Splay(u2,u1);
	Clear(P[u2].son[0]);
	P[u2].son[0]=0;
	Up(u2);
    Up(u1);
}
void MakeSame(int pos,int tot,int c){
	int u1=find(pos);
	int u2=find(pos+tot+1);
	Splay(u1,0);
	Splay(u2,u1);
	Same(P[u2].son[0],c);
	Up(u2);
	Up(u1);
}
void Reverse(int pos,int tot){
	int u1=find(pos);
	int u2=find(pos+tot+1);
	Splay(u1,0);
	Splay(u2,u1);
	Rev(P[u2].son[0]);
	Up(u2);
	Up(u1);
}
void GetSum(int pos,int tot){
	int u1=find(pos);
	int u2=find(pos+tot+1);
	Splay(u1,0);
	Splay(u2,u1);
	printf("%d\n",P[P[u2].son[0]].sum);
}
void MaxSum(){
	int u1=find(1);
	int u2=find(P[root].size);
	Splay(u1,0);
	Splay(u2,u1);
	printf("%d\n",P[P[u2].son[0]].maxsum);
}
int main(){
    scanf("%d%d",&N,&M);
    Build();
    char s[10];
    for (;M--;){
    	scanf("%s",s);
    	int pos,tot,c;
    	if (s[0]=='I'){
		    scanf("%d%d",&pos,&tot);
		    Insert(pos,tot);
		}
		if (s[0]=='D'){
		    scanf("%d%d",&pos,&tot);
		    Delete(pos,tot);
		}
		if (s[0]=='M'&&s[5]=='S'){
			scanf("%d%d%d",&pos,&tot,&c);
		    MakeSame(pos,tot,c);	
		}
		if (s[0]=='R'){
			scanf("%d%d",&pos,&tot);
			Reverse(pos,tot);
		}
		if (s[0]=='G'){
			scanf("%d%d",&pos,&tot);
			GetSum(pos,tot);
		}
		if (s[0]=='M'&&s[4]=='S')
		    MaxSum();
	}
}