记录编号	402706	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	0.270 s
提交时间	2017-05-07 16:07:37	内存使用	0.31 MiB

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <map>
#include <iostream>
using namespace std;
#define IL inline
namespace IO {
    char ch; int x, f;
    IL void qkin(int &res){
        x = 0; f = 1;
        while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
        while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;
    }
    IL void read(int &a){ qkin(a); }
    IL void read(int &a,int &b){ qkin(a), qkin(b); }
    IL void read(int &a,int &b,int &c){ qkin(a), qkin(b), qkin(c); }
}
using namespace IO;
#define siz(x) ((x) ? ((x)->size) : (0))
struct node {
	int data, key, size;
	node *ch[2];
	node(int d): data(d), size(1), key(rand()) { ch[0] = ch[1] = NULL; }
	void ref(){ size = siz(ch[0]) + siz(ch[1]) + 1; }
}*root;
void insert(int);
void insert(int,node*&);
void del(int);
void del(int,node*&);
void rot(node*&,int);
node* kth(int);
int getrk(int);

int main(){
	freopen("phs.in", "r", stdin);
	freopen("phs.out", "w", stdout);
	int n; read(n);
	int op, x;
	for(int i=1; i<=n; i++){
		read(op, x);
		if(op == 1) insert(x);
		if(op == 2) del(x);
		if(op == 3) {
			printf("%d\n", getrk(x) + 1);
		}
		if(op == 4) {
			printf("%d\n", kth(x) -> data);
		}
		if(op == 5) {
			printf("%d\n", kth(getrk(x)) -> data);
		}
		if(op == 6) {
			printf("%d\n", kth(getrk(x + 1) + 1) -> data);
		}
	}
	return 0;
}
void insert(int x){ insert(x, root); }
void insert(int x, node *&rt){
	if(!rt) { rt = new node(x); return; }
	int d = x > rt->data;
	insert(x, rt->ch[d]);
	rt->ref();
	if(rt->ch[d]->key > rt->key) rot(rt, d ^ 1);
}
void del(int x){ del(x, root); }
void del(int x, node *&rt){
	if(x == rt->data){
		if(rt->ch[0] && rt->ch[1]) {
			int d = rt->ch[0] > rt->ch[1];
			rot(rt, d); del(x, rt->ch[d]);
		} else {
			node *y = NULL;
			if(rt->ch[0]) y = rt->ch[0];
			else y = rt->ch[1];
			delete rt; rt = y;
		}
	}
	else del(x, rt->ch[x > rt->data]);
	if(rt) rt->ref();
}
void rot(node *&x, int d){
	node *y = x->ch[d ^ 1];
	x->ch[d ^ 1] = y->ch[d];
	y->ch[d] = x;
	x->ref(); y->ref();
	x = y;
}
node *kth(int x){
	node *rt = root;
	while(rt){
		if(x == siz(rt->ch[0]) + 1) return rt;
		else if(x < siz(rt->ch[0]) + 1) rt = rt->ch[0];
		else {
			x -= siz(rt->ch[0]) + 1;
			rt = rt->ch[1];
		}
	}
	return NULL;
}
int getrk(int x){
	node *rt = root; int d = 0;
	while(rt){
		if(x <= rt->data) rt = rt->ch[0];
		else {
			d += siz(rt->ch[0]) + 1;
			rt = rt->ch[1];
		}
	}
	return d;
}