记录编号	482739	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	0.309 s
提交时间	2018-01-12 14:10:55	内存使用	0.31 MiB

#include<bits/stdc++.h>
#define rr NULL
#define inf (1<<29)
#define ro son
#define RR NULL
using namespace std;
#define random org
inline int random(){
    static int seed=707; 
    return seed=int(seed*48271LL%2147483647);
}
struct Treap{
	int key,siz,val;
	Treap *son[2];
	Treap() {}
	Treap (int x){
		siz=1; key=x; val=random();
		son[0]=son[1]=rr;
	}
	void rub() {
		siz=1; 
		if (son[0]) siz+=son[0]->siz;
		if (son[1]) siz+=son[1]->siz;
	}
}; 
void split (Treap *now,int k,Treap* &x,Treap* &y){
	if (!now) { x=y=rr; return ;}
	if (now->key<=k) x=now,split(x->son[1],k,x->son[1],y);
	if (now->key> k) y=now,split(y->son[0],k,x,y->son[0]);
	now->rub();
}
Treap* kth(Treap* now,int k){
	if (k>now->siz||!k) return rr;
	int com=now->son[0]?now->son[0]->siz:0; 
	if (k<=com) return kth(now->son[0],k);
	if (k==com+1) return now;
	return kth(now->son[1],k-com-1);
} 
Treap* merge(Treap *x,Treap *y){
	if (!x) return y; if (!y) return x;
	if (x->val<y->val) {x->son[1]=merge(x->son[1],y);x->rub();return x;}
	else {y->son[0]=merge(x,y->son[0]);y->rub();return y;}
} 
int Rank(Treap *t,int k){
	int r;
	if (!t) return inf;
	if (t->son[0]==rr) 
	 r=0;else r=t->ro[0]->siz;
	if(k==t->key) return min(r+1,Rank(t->ro[0],k));
	if(k<t->key) 
	 return Rank(t->ro[0],k);
	return r+1+Rank(t->ro[1],k);
}
int Pre(Treap *t,int k){
	if (!t) return -inf;
	if (k>t->key) return max(t->key,Pre(t->ro[1],k));
	return Pre(t->ro[0],k);
}
int Sub(Treap *t,int k){
	if (!t) return inf;
	if (k<t->key) return min(t->key,Sub(t->ro[0],k));
	return Sub(t->ro[1],k);
}
int Kth(Treap *t,int k){
	int cm=0;
	if (t->ro[0]) cm=t->ro[0]->siz;  
	cm++;
	if (cm==k)
	 return t->key;
	if (cm>k) return Kth(t->ro[0],k);
	return Kth(t->ro[1],k-cm);
}
Treap* root,*x,*y,*z;
int T,op,a;
#define sight(c) ('0'<=c&&c<='9')
inline void read(int &x) {
	static char c; static int b;
	for (b=1,c=getchar();!sight(c);c=getchar()) if (c=='-') b=-1;
	for (x=0;sight(c);c=getchar()) x=x*10+c-48;
	x*=b;
}
int main () {
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	read(T);
	while (T--) {
		read(op); read(a);
		switch (op){
			case 1: split(root,a,x,y); root=merge(merge(x,new Treap(a)),y); break;
			case 2: split(root,a,x,z); split(x,a-1,x,y); 
			        if (y) y=merge(y->son[0],y->son[1]);
			        root=merge(merge(x,y),z); break;
			case 3:printf("%d\n",Rank(root,a));break;
			case 4:printf("%d\n",kth(root,a)->key);break;
			case 5:printf("%d\n",Pre(root,a));break;
			case 6:printf("%d\n",Sub(root,a));break;
		}
	}
}