记录编号	149681	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	小DOTA	是否通过	通过
代码语言	C++	运行时间	0.247 s
提交时间	2015-02-25 16:15:13	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
struct node{
	node *left,*right;
	int v,p,cnt,sz;
}*root,*null=new node((node){null,null,0,0,0,0});
void push_up(node *x)
{
	x->sz=x->left->sz+x->right->sz+x->cnt;
}
void lturn(node *&x)
{
	node *y=x->right;
	x->right=y->left; y->left=x;
	y->sz=x->sz; push_up(x); x=y;
}
void rturn(node *&x)
{
	node *y=x->left;
	x->left=y->right; y->right=x;
	y->sz=x->sz; push_up(x); x=y;
}
void Insert(node *&x,int k)
{
	if (!x->sz)
	{
		x=new node;
		x->left=x->right=null;
		x->v=k; x->p=rand();
		x->sz=x->cnt=1;
		return;
	}
	x->sz++;
	if (k==x->v) x->cnt++;
	else if (k>x->v)
	{
		Insert(x->right,k);
		if (x->right->p<x->p) lturn(x);
	}
	else
	{
		Insert(x->left,k);
		if (x->left->p<x->p) rturn(x);
	}
}
void Delete(node *&x,int k)
{
	if (!x->sz) return;
	if (k==x->v)
	{
		if (x->cnt>1) x->cnt--,x->sz--;
		else if (!x->left->sz || !x->right->sz)
		{
			node *t=x;
			if (!x->left->sz) x=x->right;
			else x=x->left;
			delete t;
		}
		else if (x->left->p<x->right->p)
			rturn(x),Delete(x,k);
		else lturn(x),Delete(x,k);
	}
	else if (k<x->v) x->sz--,Delete(x->left,k);
	else x->sz--,Delete(x->right,k);
}
int query_rank(node *x,int k)
{
	if (!x->sz) return 0;
	if (k==x->v) return x->left->sz+1;
	else if (k<x->v) return query_rank(x->left,k);
	else return query_rank(x->right,k)+x->left->sz+x->cnt;
}
int query_num(node *x,int k)
{
	if (!x->sz) return 0;
	if (k<=x->left->sz) return query_num(x->left,k);
	else if (k>x->left->sz+x->cnt)
		return query_num(x->right,k-x->left->sz-x->cnt);
	else return x->v;
}
int query_pro(node *x,int k,int c)
{
	if (!x->sz) return c;
	if (k>x->v) return query_pro(x->right,k,x->v);
	else return query_pro(x->left,k,c);
}
int query_succ(node *x,int k,int c)
{
	if (!x->sz) return c;
	if (k<x->v) return query_succ(x->left,k,x->v);
	else return query_succ(x->right,k,c);
}
int main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	int q;
	scanf("%d",&q);
	root=null;
	srand(time(0));
	while (q--)
	{
		int opt,x;
		scanf("%d%d",&opt,&x);
		switch (opt)
		{
			case 1:Insert(root,x); break;
			case 2:Delete(root,x); break;
			case 3:printf("%d\n",query_rank(root,x)); break;
			case 4:printf("%d\n",query_num(root,x)); break;
			case 5:printf("%d\n",query_pro(root,x,0)); break;
			case 6:printf("%d\n",query_succ(root,x,0)); break; 
		}
	}
	return 0;
}