记录编号	425327	评测结果	RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
题目名称	[HZOI 2016]tb的平衡树	最终得分	0
用户昵称	하루Kiev	是否通过	未通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-07-15 08:20:27	内存使用	1.46 MiB

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<time.h>
#define maxn 50005
#define inf 0x3f3f3f3f
using namespace std;
struct tree{
	int l,r,no,size,tot,rd;
}e[maxn];int zz,root,n,opt,s,fro,bac;
void l_swap(int &root){
	 int newroot=e[root].r;
	 e[root].r=e[newroot].l;
	 e[newroot].l=root;
	 e[newroot].size=e[root].size;
	 e[root].size=e[e[root].l].size+e[e[root].r].size+e[root].tot;
	 root=newroot;
}
void r_swap(int &root){
	 int newroot=e[root].l;
	 e[root].l=e[newroot].r;
	 e[newroot].r=root;
	 e[newroot].size=e[root].size;
	 e[root].size=e[e[root].l].size+e[e[root].r].size+e[root].tot;
	 root=newroot;
}
void insert_(int &root,int x){
     if(!root){
     	root=++zz;
     	e[root].no=x;
     	e[root].size=e[root].tot=1;
     	e[root].rd=rand();//随机数维护堆性质 
     	return;
     }
     e[root].size++;
     if(e[root].no==x) e[root].tot++;
     else{
	     if(e[root].no>x){
	     	insert_(e[root].l,x);
	     	if(e[e[root].l].rd<e[root].rd)
              r_swap(root);
         }
         else{
         	insert_(e[root].r,x);
         	if(e[e[root].r].rd<e[root].rd)
         	   l_swap(root);
         
		 }
	}
}
void delete_(int &root,int no){
     if(!root) return;
     if(e[root].no==no){
     	if(e[root].tot>1){
		   e[root].tot--;
		   e[root].size--;
		   return;
	    }//有很多个相同数，删除一个不影响树的结构
     	if(e[root].l*e[root].r==0) root=e[root].l+e[root].r;//子树只有一个，直接抬升子树节点
        else{
		   if(e[e[root].l].rd<e[e[root].r].rd)
		      r_swap(root);
		   else l_swap(root);
		   //维护堆性质后，继续删除节点 
	       delete_(root,no);
		}
     }
     else{
     	 e[root].size--;
     	 if(no>e[root].no) delete_(e[root].r,no);
     	 else delete_(e[root].l,no); 
     }
}	
void anc_(int &root,int no){
	 if(!root) return;
	 if(e[root].no<no){
	 	fro=e[root].no;
	 	anc_(e[root].r,no);
	 }
	 else anc_(e[root].l,no);
}
void bac_(int &root,int no){
	 if(!root) return;
	 if(e[root].no>no){
	 	bac=e[root].no;
	 	bac_(e[root].l,no);
	 }
	 else bac_(e[root].r,no);
}
int rank_(int &root,int no){
     if(!root) return 0;
     if(e[root].no==no){
     	return e[e[root].l].size+1;
     }
     else if(e[root].no>no) return rank_(e[root].l,no);
	      else return e[e[root].l].size+e[root].tot+rank_(e[root].r,no);
}
int num_(int &root,int rank){
	if(!root) return 0;
	if(e[e[root].l].size+1<=rank&&e[e[root].l].size+e[root].tot>=rank)
	   return e[root].no;
	if(e[e[root].l].size>=rank) return num_(e[root].l,rank);	
    if(e[e[root].l].size<rank)  return num_(e[root].r,rank-e[root].tot-e[e[root].l].size);
    
}	
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	scanf("%d",&n);
	while(n--){
	      scanf("%d%d",&opt,&s);
		  switch(opt){
		         case 1: insert_(root,s);break;
				 case 2: delete_(root,s);break;
				 case 3: printf("%d\n",rank_(root,s));break;
				 case 4: printf("%d\n",num_(root,s));break;
				 case 5: fro=-inf;anc_(root,s);printf("%d\n",fro);break;
				 case 6: bac=-inf;bac_(root,s);printf("%d\n",bac);break;
		  }
	}
    //system("pause");
	return 0; 
}