记录编号	501419	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	_WA自动机	是否通过	通过
代码语言	C++	运行时间	0.263 s
提交时间	2018-07-21 20:41:21	内存使用	0.31 MiB

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<climits>
#include<cstdlib>
#include<ctime>
struct node
{
	int v,cnt,rank,s;
	node *ch[2];
	node(int v):v(v),cnt(1),s(1),rank(rand()){ch[0]=ch[1]=0;}
	void MT()
	{
		s=cnt;
		if (ch[0]) s+=ch[0]->s;
		if (ch[1]) s+=ch[1]->s;
	}
	int cmp(int x)
	{
		if (x==v) return -1;
		return v<x;
	}
}*root;
void rotate(node* &o,int d)
{
	node* k=o->ch[d^1];
	o->ch[d^1]=k->ch[d];
	k->ch[d]=o;
	o->MT();
	k->MT();
	o=k;
}
void insert(node* &o,int v)
{
	if (!o) {o=new node(v);return;}
	int d=o->cmp(v);
	if (d==-1) {++o->cnt;++o->s;return;}
	insert(o->ch[d],v);
	if (o->ch[d]->rank>o->rank) rotate(o,d^1);
	o->MT();
}
void remove(node* &o,int v)
{
	int d=o->cmp(v);
	if (d==-1)
	{
		if (o->cnt>1) {--o->cnt;--o->s;return;}
		if (!(o->ch[0])) {node* k=o;o=o->ch[1];delete k;}
		else if (!(o->ch[1])) {node* k=o;o=o->ch[0];delete k;}
		else
		{
			int d2=o->ch[0]->rank>o->ch[1]->rank;
			rotate(o,d2);
			remove(o->ch[d2],v);
		}
	}
	else remove(o->ch[d],v);
	if (o) o->MT();
}
int rank(int x,node* o=root)
{
	if (!o) return INT_MAX;
	int s=o->ch[0]?o->ch[0]->s:0;
	if (o->v==x) return s+1;
	if (o->v>x) return rank(x,o->ch[0]);
	if (o->v<x) return rank(x,o->ch[1])+s+o->cnt; 
}
int kth(int k,node* o=root)
{
	if (!o) return INT_MIN;
	int s=o->ch[0]?o->ch[0]->s:0;
	if (k>s && k<=s+o->cnt) return o->v;
	if (k<=s) return kth(k,o->ch[0]);
	return kth(k-s-o->cnt,o->ch[1]);
}
int prec,succ;
void pre(int x,node* o=root)
{
	if (!o) return;
	if (o->v>prec && o->v<x) prec=o->v;
	if (o->v>=x) pre(x,o->ch[0]);
		else pre(x,o->ch[1]); 
}
void suc(int x,node* o=root)
{
	if (!o) return;
	if (o->v<succ && o->v>x) succ=o->v;
	if (o->v<=x) suc(x,o->ch[1]);
		else suc(x,o->ch[0]);
}
int main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	srand(time(0));
	int n;
	int opt,x;
	scanf("%d",&n);
	while (n--)
	{
		scanf("%d%d",&opt,&x);
		switch (opt)
		{
			case 1:insert(root,x);break;
			case 2:remove(root,x);break;
			case 3:printf("%d\n",rank(x));break;
			case 4:printf("%d\n",kth(x));break;
			case 5:prec=INT_MIN;pre(x);printf("%d\n",prec);break;
			case 6:succ=INT_MAX;suc(x);printf("%d\n",succ);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}