[Tyvj 1728]普通平衡树 - Hzoi_ - 284925

记录编号	284925	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.149 s
提交时间	2016-07-20 11:03:13	内存使用	1.81 MiB
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{//AVL Balanced Tree
	int data,size,h;
	node *lch,*rch,*prt;
	node(int d=0):data(d),size(1),h(1),lch(NULL),rch(NULL),prt(NULL){}
	void refresh(){
		size=h=1;
		if(lch){
			size+=lch->size;
			h=max(h,lch->h+1);
		}
		if(rch){
			size+=rch->size;
			h=max(h,rch->h+1);
		}
	}
	int bal(){
		if(lch&&rch)return lch->h-rch->h;
		if(lch&&!rch)return lch->h;
		if(!lch&&rch)return -rch->h;
		return 0;
	}
};
node *root=NULL;
node *newnode(int=0);
void insert(node*,node* =root);
node *find(int,node* =root);
void del(node*);
node *prev(node*);
node *succ(node*);
void lrot(node*);
void rrot(node*);
node *findmin(node* =root);
node *findmax(node* =root);
int rank(int,node* =root);
node *kth(int,node* =root);
int previous(int,node* =root);
int succeeding(int,node* =root);
int n,opt,x;
node *y;
int main(){
#define MINE
#ifdef MINE
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
#endif
	scanf("%d",&n);
	while(n--){
		scanf("%d%d",&opt,&x);
		if(opt==1){//1.插入x数
			insert(newnode(x));
		}
		else if(opt==2){//2.删除x数(若有多个相同的数，只删除一个)
			del(find(x));
		}
		else if(opt==3){//3.查询x数的排名(若有多个相同的数，输出最小的排名)
			printf("%d\n",rank(x));
		}
		else if(opt==4){//4.查询排名为x的数
			y=kth(x);
			if(!y)printf("-1\n");
			else printf("%d\n",y->data);
		}
		else if(opt==5){//5.求x的前驱(前驱定义为小于x，且最大的数)
			printf("%d\n",previous(x));
		}
		else if(opt==6){//6.求x的后继(后继定义为大于x，且最小的数)
			printf("%d\n",succeeding(x));
		}
	}
	return 0;
}
node *newnode(int d){
	return new node(d);
}
void insert(node *x,node *rt){
	if(!root){
		root=x;
		return;
	}
	for(;;){
		if(x->data<rt->data){
			if(rt->lch)rt=rt->lch;
			else{
				rt->lch=x;
				break;
			}
		}
		else{
			if(rt->rch)rt=rt->rch;
			else{
				rt->rch=x;
				break;
			}
		}
	}
	x->prt=rt;
	//Insert Balance
	while(rt){
		rt->refresh();
		if(rt->bal()==2){//L
			x=rt->lch;
			if(x->bal()==1){//LL
				rrot(rt);
			}
			else{//LR
				lrot(x);
				rrot(rt);
			}
			rt=rt->prt;
		}
		else if(rt->bal()==-2){//R
			x=rt->rch;
			if(x->bal()==-1){//RR
				lrot(rt);
			}
			else{//RL
				rrot(x);
				lrot(rt);
			}
			rt=rt->prt;
		}
		rt=rt->prt;
	}
}
node *find(int x,node *rt){
	while(rt){
		if(x==rt->data)return rt;
		if(x<rt->data)rt=rt->lch;
		else rt=rt->rch;
	}
	return NULL;
}
void del(node *x){
	if(x->lch&&x->rch){
		node *y=prev(x);
		x->data=y->data;
		del(y);
	}
	else{
		if(x->lch&&!x->rch){
			x->lch->prt=x->prt;
			if(x->prt){
				if(x==x->prt->lch)x->prt->lch=x->lch;
				else x->prt->rch=x->lch;
			}
			else root=x->lch;
		}
		else if(!x->lch&&x->rch){
			x->rch->prt=x->prt;
			if(x->prt){
				if(x==x->prt->lch)x->prt->lch=x->rch;
				else x->prt->rch=x->rch;
			}
			else root=x->rch;
		}
		else{
			if(x->prt){
				if(x==x->prt->lch)x->prt->lch=NULL;
				else x->prt->rch=NULL;
			}
			else root=NULL;
		}
		//Delete Balance
		node *rt=x->prt;
		delete x;
		for(;rt;rt=rt->prt){
			rt->refresh();
			if(rt->bal()==2){//L
				x=rt->lch;
				if(x->bal()==1){//LL
					rrot(rt);
				}
				else if(x->bal()==-1){//LR
					lrot(x);
					rrot(rt);
				}
				else{//LE
					rrot(rt);
				}
				rt=rt->prt;
			}
			else if(rt->bal()==-2){//R
				x=rt->rch;
				if(x->bal()==-1){//RR
					lrot(rt);
				}
				else if(x->bal()==1){//RL
					rrot(x);
					lrot(rt);
				}
				else{//RE
					lrot(rt);
				}
				rt=rt->prt;
			}
		}
	}
}
node *prev(node *x){
	if(!x->lch)return NULL;
	for(x=x->lch;x->rch;x=x->rch);
	return x;
}
node *succ(node *x){
	if(!x->rch)return NULL;
	for(x=x->rch;x->lch;x=x->lch);
	return x;
}
void lrot(node *x){
	if(!x)return;
	node *y=x->rch;
	if(!y)return;
	y->prt=x->prt;
	if(x->prt){
		if(x==x->prt->lch)x->prt->lch=y;
		else x->prt->rch=y;
	}
	else root=y;
	x->prt=y;
	x->rch=y->lch;
	if(y->lch)y->lch->prt=x;
	y->lch=x;
	x->refresh();
	y->refresh();
}
void rrot(node *x){
	if(!x)return;
	node *y=x->lch;
	if(!y)return;
	y->prt=x->prt;
	if(x->prt){
		if(x==x->prt->lch)x->prt->lch=y;
		else x->prt->rch=y;
	}
	else root=y;
	x->prt=y;
	x->lch=y->rch;
	if(y->rch)y->rch->prt=x;
	y->rch=x;
	x->refresh();
	y->refresh();
}
node *findmin(node *rt){
	if(!rt)return NULL;
	while(rt->lch)rt=rt->lch;
	return rt;
}
node *findmax(node *rt){
	if(!rt)return NULL;
	while(rt&&rt->rch)rt=rt->rch;
	return rt;
}
int rank(int x,node *rt){
	int ans=0;
	while(rt){
		if(rt->data<x){
			if(rt->lch)ans+=rt->lch->size;
			ans++;
			rt=rt->rch;
		}
		else rt=rt->lch;
	}
	return ans+1;
}
/*这个是wmd神犇的代码，看到之后茅塞顿开
int rank(int t){//t的排名(算上哨兵,<t的个数)
	int now=root,ans=0;
	while(now){
		if(key(now)<t) ans+=sz(l(now))+1,now=r(now);
		else now=l(now);
	}
	return ans;
}
*/
node *kth(int x,node *rt){
	if(!rt||x<1||x>rt->size)return NULL;
	if(rt->lch){
		if(x<=rt->lch->size)return kth(x,rt->lch);
		if(x==rt->lch->size+1)return rt;
		return kth(x-rt->lch->size-1,rt->rch);
	}
	if(x==1)return rt;
	return kth(x-1,rt->rch);
}
int previous(int x,node *rt){//小于x,且最大的数
	if(!rt)return -0x7ffffff;
	if(x<=rt->data)return previous(x,rt->lch);
	else return max(rt->data,previous(x,rt->rch));//rt->data<x
}
int succeeding(int x,node *rt){//大于x,且最小的数
	if(!rt)return 0x7ffffff;
	if(x>=rt->data)return succeeding(x,rt->rch);
	else return min(rt->data,succeeding(x,rt->lch));//rt->data>x
}