记录编号	431363	评测结果	AAAAAAAAAA
题目名称	1829.[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	joel	是否通过	通过
代码语言	C++	运行时间	0.291 s
提交时间	2017-07-31 17:10:01	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cctype>
using namespace std;
const int INF = 10000000;

inline int readint(){
	char c = getchar();
	int f = 1;
	while(!isdigit(c)){
		if(c == '-') f = -1;
		c = getchar();
	}
	int x = 0;
	while(isdigit(c))
		x = x*10 + c-'0',c = getchar();
	return x*f;
}
int buf[10];
inline void writeint(int x){
	if(x < 0) putchar('-'),x = -x;
	int cnt = 0;
	if(x == 0)
		buf[cnt++] = 0;
	else while(x)
		buf[cnt++] = x%10,x /= 10;
	for(int i = cnt-1;i >= 0;i--) 
		putchar('0'+buf[i]);
	putchar(' ');
}
inline void pcn(){ putchar('\n');}

class Node{
public:
	Node *left,*right;
	int val,r,size;
	Node():left(NULL),right(NULL),val(0),r(-1),size(0){}
	void Maintain(){
		size = 1;
		if(left != NULL)  size += left->size;
		if(right != NULL) size += right->size;
	}
}*root=NULL;

void Right_Rotate(Node* &p){
	Node* k = p->left;
	p->left = k->right;
	k->right = p;
	p->Maintain(),k->Maintain();
	p = k;
}
void Left_Rotate(Node* &p){
	Node* k = p->right;
	p->right = k->left;
	k->left = p;
	p->Maintain(),k->Maintain();
	p = k;
}

void INS(Node* &p,int x){
	if(p == NULL){
		p = new Node;
		p->left = NULL;
		p->right = NULL;
		p->val = x;
		p->r = rand();
	}
	else{
		if(x < p->val){
			INS(p->left,x);
			if(p->r < p->left->r)
				Right_Rotate(p);
		}else{
			INS(p->right,x);
			if(p->r < p->right->r)
				Left_Rotate(p);
		}
	}
	p->Maintain();
}
void DEL(Node* &p,int x){
	if(p->val == x){
		if(p->left == NULL)
			p = p->right;
		else if(p->right == NULL)
			p = p->left;
		else {
			if(p->left->r > p->right->r){
				Right_Rotate(p);
				DEL(p->right,x);
			}else {
				Left_Rotate(p);
				DEL(p->left,x);
			}
		}
	}
	else {
		if(x < p->val)
			DEL(p->left,x);
		else 
			DEL(p->right,x);
	}
	if(p != NULL) p->Maintain();
}

int RANK(Node* p,int x){
	int ans = 1;
	while(p != NULL){
		if(x > p->val){
			if(p->left != NULL)
				ans += p->left->size;
			ans++;
			p = p->right;
		} else 
			p = p->left;
	}
	return ans;
}
int QUE(Node* p,int x){
	if(p == NULL||x <= 0||x > p->size)
		return 0;
	int s = (p->left == NULL? 1 : p->left->size + 1);
	if(s == x)
		return p->val;
	else if(x < s)
		return QUE(p->left,x);
	else 
		return QUE(p->right,x-s);
}

int PRO(Node *p,int x){
	int ans = -INF-10;
	while(p != NULL){
		if(p->val < x){
			ans = max(ans,p->val);
			p = p->right;
		}else 
			p = p->left;
	}
	return ans;
}
int SUC(Node* p,int x){
	int ans = INF+10;
	while(p != NULL){
		if(p->val > x){
			ans = min(ans,p->val);
			p = p->left;
		}else 
			p = p->right;
	}
	return ans;
}
int main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	int n,opt,x; n = readint();
	while(n--){
		opt = readint(),x = readint();
		switch(opt){
		case 1:INS(root,x); break;
	    case 2:DEL(root,x); break;
		case 3:writeint(RANK(root,x));pcn();break;
		case 4:writeint(QUE(root,x)); pcn(); break;
		case 5:writeint(PRO(root,x)); pcn(); break;
		case 6:writeint(SUC(root,x)); pcn(); break;
		}
	}
	return 0;
}