记录编号	281109	评测结果	AAAAAA
题目名称	[POJ 1442] 黑盒子	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.048 s
提交时间	2016-07-11 07:58:28	内存使用	0.54 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30010;
struct node{//AVL Balanced Tree
	int data,size,h;//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和高度(高度是AVL专属)
		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(){//返回节点的平衡因子(左子树的高度减去右子树的高度),当然这是AVL专属
		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,m,a[maxn],b[maxn];
node *x;
int main(){
#define MINE
#ifdef MINE
	freopen("blackbox.in","r",stdin);
	freopen("blackbox.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d",&b[i]);
	b[0]=1;
	for(int i=1;i<=n;i++){
		insert(newnode(a[i]));
		while(b[b[0]]==i){
			x=kth(b[0]++);//查询排名为i的数
			if(x)printf("%d\n",x->data);
			else printf("0\n");
		}
	}
	return 0;
}
node *newnode(int d){//返回一个指向新节点的指针
	return new node(d);
}
void insert(node *x,node *rt){//把x插入到以rt为根的子树中
	if(!root){//如果当前树为空,直接把根设为x
		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;
	//后面是AVL的插入平衡相关,看不懂就别看了= =
	//总之别忘了往上维护size值(这里是借助refresh函数进行的)
	//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){//L
			x=rt->rch;
			if(x->bal()==-1){//RR
				lrot(rt);
			}
			else{//RL
				rrot(x);
				lrot(rt);
			}
			rt=rt->prt;
		}
		rt=rt->prt;
	}
	//AVL的插入有四种情况......
}
node *find(int x,node *rt){//普通的查找算法,返回值为x的节点的位置
	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){//更新x的父亲的儿子指向的位置
				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;
		}
		//以下是AVL的删除平衡......
		//还是如果看不懂就不要看,
		//但要记得往上走更新size值(这里还是利用refresh函数) 
		//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;
			}
		}
		//AVL树的删除有6种情况......不过每种情况的代码都很好写,
		//并且也不容易漏掉,所以正确率还是有保障的
	}
}
node *prev(node *x){//这个不是真的前驱......只是左子树的最大值
	//(实际中可能会出现它的前驱是它的父亲的情况)
	if(!x->lch)return NULL;
	for(x=x->lch;x->rch;x=x->rch);
	return x;
}
void lrot(node *x){//左旋,具体可以看SBT的资料,各种需要旋转的平衡树都是互通的
	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 *kth(int x,node *rt){//返回以rt为根的子树中第x大的元素,
	//具体讲解就不啰嗦了,自己体会妙处吧
	if(x==1)return findmin(rt);
	if(rt->lch&&rt->lch->size==x-1)return rt;
	if(rt->lch&&rt->lch->size>=x)return kth(x,rt->lch);
	else if(rt->lch)return kth(x-rt->lch->size-1,rt->rch);
	else return kth(x-1,rt->rch);
}
//代码很长......也是因为我的代码风格是拆分各种情况分别处理,显得很啰嗦...