记录编号	264661	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	粘粘自喜	是否通过	通过
代码语言	C++	运行时间	0.914 s
提交时间	2016-05-29 20:57:30	内存使用	13.51 MiB

#include<iostream>
#include<cstdio>
using namespace std;
struct node{
	int key,sz,cnt;
	int sum;
	node(){}
	node *ch[2],*pre;
	node(int x,int y,int z){
	 key=x;sz=y;cnt=z;
	}
	void rs()
	{
		sz=ch[0]->sz+ch[1]->sz+cnt;
	}
}nil(0,0,0),*NIL=&nil;
node *root,nod[1000000+100];
int ncnt;
void init()
{
	ncnt=0;
	root=NIL;
}
void update(node *x,int c)
{
	x->sum=x->ch[1]->sum+x->ch[0]->sum;
}
void Rotate(node *x,int c)
{
	node *y=x->pre;
	y->ch[!c]=x->ch[c];
	if(x->ch[c]!=NIL){x->ch[c]->pre=y;}
	x->pre=y->pre;
	if(y->pre!=NIL)
		if(y->pre->ch[c]==y) {
			y->pre->ch[c]=x;
		}
		else y->pre->ch[!c]=x;
	x->ch[c]=y;y->pre=x;
	x->rs();
	y->rs();
	update(y,!c);
	update(x,c);
}
void Splay(node *x,node *f)
{
	node *y;
	while(x->pre!=f)
	{
		y=x->pre;
		if(x==y->ch[0])
		{
			if(y->pre!=f&&y==y->pre->ch[0]) Rotate(y,1);
			Rotate(x,1);
		}
		else{  
                if (y->pre != f && y == y->pre->ch[1])  
                    Rotate(y, 0);  
                    Rotate(x, 0);  
            }  
        }  
        if (f == NIL)  
            root = x;  
}  
void insert(int key)
{
	if(root==NIL)
	{
		ncnt = 0;
        root = &nod[++ncnt];
		root->ch[0]=root->ch[1]=root->pre=NIL;
		root->key=key;
		root->sz=root->cnt=1;
		root->sum=key;
		return ;
	}
	node *x=root,*y;
	while(1)
	{
		x->sz++;
		if(key==x->key)
		{
			x->cnt++;
			x->rs();
			y=x;
			break;
		}
		else if(key<x->key)
		{
			if(x->ch[0]!=NIL)
			{
				x=x->ch[0];
			}
			else{
				x->ch[0] = &nod[++ncnt];
				y=x->ch[0];
				y->key=key;
				y->sz=y->cnt=1;
				y->ch[0]=y->ch[1]=NIL;
				y->pre=x;
				y->sum=key;
				break;
			}
		
		}
		else {
			if(x->ch[1]!=NIL)
			{
				x=x->ch[1];
			}
			else {
				x->ch[1] = &nod[++ncnt];
				y=x->ch[1];
				y->key=key;
				y->sz=y->cnt=1;
				y->ch[0]=y->ch[1]=NIL;
				y->pre=x;
				y->sum=key;
				break ;
			}
		}
	}
	Splay(y,NIL);
}
node *Search(int key)
{
	if(root==NIL) return NIL;
	node *x=root,*y=NIL;
	while(1)
	{
		if(key==x->key) {y=x;break;}
		else if(key>x->key)
		{
			if(x->ch[1]!=NIL)
				x=x->ch[1];
			else break;
		}
		else {
			if(x->ch[0]!=NIL)
				x=x->ch[0];
			else break;
		}
	}
	Splay(x,NIL);
	return y;
}
node *searchmin(node *x)
{
	node *y=x->pre;
	while(x->ch[0]!=NIL) x=x->ch[0];
	Splay(x,y);
	return x;
}
void del(int key){
        if (root == NIL)  
        return;  
        node *x = Search(key), *y;  
        if (x == NIL)  
            return;  
        if (x->cnt > 1){  
            x->cnt--;  
            x->rs();  
            return;  
        }  
        else if (x->ch[0] == NIL && x->ch[1] == NIL){  
            init();  
            return;  
        }  
        else if (x->ch[0] == NIL){  
            root = x->ch[1];  
            x->ch[1]->pre = NIL;  
            return;  
        }  
        else if (x->ch[1] == NIL){  
            root = x->ch[0];  
            x->ch[0]->pre = NIL;  
            return;  
        }  
        y = searchmin(x->ch[1]);  
        y->pre = NIL;  
        y->ch[0] = x->ch[0];  
        x->ch[0]->pre = y;  
        y->rs();  
        root = y;  
    } 
node* findk(int kth){
        if (root == NIL || kth > root->sz)  
            return NIL;  
        node *x = root;  
        while (1){  
            if (x->ch[0]->sz +1 <= kth && kth <= x->ch[0]->sz + x->cnt)  
                break;  
            else if (kth <= x->ch[0]->sz)  
                x = x->ch[0];  
            else{  
                kth -= x->ch[0]->sz + x->cnt;  
                x = x->ch[1];  
            }  
        }  
        Splay(x, NIL);  
        return x;  
    } 
int getb(int key)
{
	insert(key);
	node *x=Search(key);
	node *y=x->ch[0];
	if(y==NIL) {
		del(key);
		return x->pre->key;
	}
	else{
		while(y->ch[1]!=NIL) y=y->ch[1];
		del(key);
		return y->key;
	}
	
}
int getn(int key)
{
	insert(key);
	node *x=Search(key);
	node *y=x->ch[1];
	if(y==NIL) {
		del(key);
		return x->pre->key;
	}
	else{
		while(y->ch[0]!=NIL) y=y->ch[0];
		del(key);
		return y->key;
	}
}
int getnum(int key)
{
	insert(key);
	long long  a=Search(key)->ch[0]->sz+1;
	del(key);
	return a;
}
int Main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	init();
    int num;
    cin>>num;
    while(num--)
    {
    	int a,b;
    	cin>>a>>b;
    	if(a==1) insert(b);
    	if(a==2) del(b);
    	if(a==3) cout<<getnum(b)<<endl;
    	if(a==4) cout<<findk(b)->key<<endl;
    	if(a==5) cout<<getb(b)<<endl;
    	if(a==6) cout<<getn(b)<<endl;
	}
	
	return 0;
}
int main(){;}
int icandoit=Main();