评测记录

#include <stdio.h>
#define il inline
using namespace std;
const int N=100005;
struct tree{
	int s[2]; //左儿子0右儿子1
	int p;    //父节点
	int v;    //结点权值
	int cnt;  //该节点出现次数
	int siz;  //子树大小
	il void init(int p1,int v1){ //初始化
		p=p1,v=v1;
		cnt=siz=1;
	}
}t[N];
int root; //根节点
int idx=0; //节点数量

il void pushup(int x){
	t[x].siz=t[t[x].s[0]].siz+t[t[x].s[1]].siz+t[x].cnt;
	//旋转后更新子树大小
}

il void rotate(int x){
	int y=t[x].p,z=t[y].p;
	//x节点的爹和爷
	int k=(t[y].s[1]==x);
	//k为旋转情况，依x所在位置判断，为0右移，为1左移
	t[y].s[k]=t[x].s[k^1];
	t[t[x].s[k^1]].p=y;
	//关于x儿子的旋转
	t[x].s[k^1]=y;
	t[y].p=x;
	//父子关系对调
	t[z].s[t[z].s[1]==y]=x;
	t[x].p=z;
	//更新爷的关系
	pushup(y);
	pushup(x);
}

il void splay(int x,int k){
	//把x转到k的下面，即k的儿子
	//若k==0则转到根
	while(t[x].p!=k){
		int y=t[x].p,z=t[y].p;
		if(z!=k){
			if((t[z].s[0]==y)^(t[y].s[0]==x))
				//判断是直线还是折线
				rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	if(k==0) root=x;
}

il void find(int v){
	//找到v所在节点并将其转到根
	int x=root;
	while(t[x].s[x>t[x].v] && v!=t[x].v){
		//结束条件：走到空节点或找到该节点
		x=t[x].s[x>t[x].v];
	}
	splay(x,0);
}

il int get_front(int v){
	//查询v的前驱，并返回其节点编号
	find(v);
	int x=root;
	if(t[x].v<v) return x; 
	x=t[x].s[0];
	while(t[x].s[1]) x=t[x].s[1]; 
	splay(x,0);
	return x;
}

il int get_back(int v){
	//查询v的后继
	find(v);
	int x=root;
	if(t[x].v>v) return x;
	x=t[x].s[1];
	while(t[x].s[0]) x=t[x].s[0];
	splay(x,0);
	return x;
}

il void del(int v){
	//删除v，如果有多个相同的数，则只删除一个
	int front=get_front(v);   //printf("___\n");
	int back=get_back(v);
	splay(front,0);   //printf("___\n");
	splay(back,front);
	int deel=t[back].s[0];  //printf("***\n");
	if(t[deel].cnt>1){
		t[deel].cnt--;
		//有多个相同就减一
		splay(deel,0);
		//这里的splay是为了更新
	}
	else{
		t[back].s[0]=0;
		//否则就变味空节点，即删除
		splay(back,0);
		//这里splay同理
	}
}

il void insert(int v){
	//把v插入
	int x=root,p=0;
	while(x && t[x].v!=v){
		p=x;
		x=t[x].s[v>t[x].v];
	}
	if(x) t[x].cnt++;
	else{
		x=++idx;
		t[p].s[v>t[p].v]=x;
		t[x].init(p,v);
	}
	splay(x,0);
}

il int get_rank(int v){
	//查找v的排名
	insert(v);
//	printf("%%%\n");
	int res=t[t[root].s[0]].siz;
	del(v);
	return res;
}

il int get_val(int k){
	//查找排名为k的数
	int x=root;
	while(1){
		int y=t[x].s[0];
		if(t[y].siz+t[x].cnt<k){
			k-=(t[y].siz+t[x].cnt);
			x=t[x].s[1];
		}
		else{
			if(t[y].siz>=k) x=t[x].s[0];
			else break;
		}
	}
	splay(x,0);
	return t[x].v;
}

int main(){
	insert(1e9);
	insert(-1e9);
	int n;
	scanf("%d",&n);
	while(n--){
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(opt==1) insert(x);
		if(opt==2) del(x);
		if(opt==3) printf("%d\n",get_rank(x));
//		if(opt==3) while(1);
		if(opt==4) printf("%d\n",get_val(x+1));
		if(opt==5) printf("%d\n",t[get_front(x)].v);
		if(opt==6) printf("%d\n",t[get_back(x)].v);
	}
}
/*
  5
  1 24
  1 25
  1 20
  3 23
  3 23

 */