$rt$

#6~#11re

记录

qwq

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2000010;
int m;
int root;//根节点编号，旋转时会变化
int idx;//节点个数 
struct Node
{
	int s[2];//左右儿子，方便把左旋和右旋写在一个函数里
	int p;//父节点
	int v;//节点权值
	int cnt;//该权值出现的次数，避免相同权值存多个点
	int size;//子树大小
	void init(int p1,int v1)
	{
		p=p1,v=v1;
		cnt=size=1;
	} 
}tree[N];
void pushup(int x)//更新x的子树（含x自己）的大小 
{
	tree[x].size=tree[tree[x].s[0]].size+tree[tree[x].s[1]].size+tree[x].cnt;
} 
//对x进行旋转，x是左儿子则右旋，x是右儿子则左旋 
void rotate(int x)
{
	int y=tree[x].p,z=tree[y].p;//x的父亲和爷爷
	
	int k = tree[y].s[1]==x;//x是右儿子则k=1，x是左儿子则k=0
	tree[y].s[k]=tree[x].s[k^1];
	tree[tree[x].s[k^1]].p=y;//注意一次更改操作需要改对应的两个点
	//把x刚刚空出来的儿子变成y 
	tree[x].s[k^1]=y;
	tree[y].p=x;
	//把x替换到原来y的位置 
	//如果原来y是z的右儿子，则把x改成z的右儿子，反之同理 
	tree[z].s[tree[z].s[1]==y]=x;
	tree[x].p=z;
	pushup(y),pushup(x);//y在下面，从下向上更新子树大小 
}
//把x旋转到k的下面（k=0时就旋转到根节点）
void splay(int x,int k)
{
	while(tree[x].p!=k)
	{
		int y=tree[x].p,z=tree[y].p;
		
		if(z!=k) //折转底，直转中
			((tree[y].s[0]==x)^(tree[z].s[0]==y))?//x和y同方向则为真，异方向则为假
			rotate(x):rotate(y);
		rotate(x); 
	}
	if(k==0) root=x;//x转到根记得换根 
}
//查找：找到权值为v的节点，并把该节点转到根
void find(int v)
{
	int x=root;//从根向下找
	//v>tree[x].v为真则向左子树即tree[0]找，为假则向右子树即tree[1]找 
	//故tree[x].s[v>tree[x].v]即为下一个要找的节点 
	while(tree[x].s[v>tree[x].v]/*下一个节点为空时退出，即在权值为v的点不存在的时候找到与v最接近的点（可大可小），找前驱和后继有用*/
	&&tree[v].v!=v/*找到权值为v的点退出*/)
		x=tree[x].s[v>tree[x].v];
	splay(x,0);
}
//求权值为v的前驱节点，返回其节点编号
int get_pre(int v)
{
	find(v);
	int x=root;
	if(tree[x].v<v) return x;
	//在v不存在的情况下，如果恰好找到的是比v小的点，那这个点就是所求前驱
	//                   如果找到的是比v大的点，则v的前驱也就是该点的前驱，与相等执行一样的操作 
	x=tree[x].s[0];//所求前驱即为x的左子树的最右边 
	while(tree[x].s[1]) x=tree[x].s[1];//不断找右子树，直到右子树为空
	/*为什么 此时平衡性应该没变才对*/splay(x,0);//再splay保证复杂度 
	return x; 
}
int get_suf(int v)
{
	find(v);
	int x=root;
	if(tree[x].v>v) return x;//同上，恰好找到比v大的点
	x=tree[x].s[1];//后缀即为x的右子树的最左边
	while(tree[x].s[0]) x=tree[x].s[0];
	splay(x,0);
	return x; 
}
//删除权值为v的节点（若有多个相同的数，只删除一个） 
void del(int v)
{
	int pre=get_pre(v),suf=get_suf(v);
	//把前驱节点转到根，再把后继节点转到前驱节点下面（因为比前驱大，一定是其右儿子） 
	splay(pre,0),splay(suf,pre);
	//要删除的点比前驱大，又比后继小，现在一定在后继的左儿子上 
	const int del=tree[suf].s[0];
	if(tree[del].cnt>1)
		tree[del].cnt--,splay(del,0);
		//此时splay目的：通过其中的pushup更新受影响的子树大小 
	else 
		tree[suf].s[0]=0,splay(suf,0); 
}
//插入一个数值为v的节点 
void insert(int v)
{
	int x=root,p=0;//p:x的父节点 
	while(x/*找到下一个点为0是退出，对应插入的v不存在的情况*/&&tree[x].v!=v)
		p=x,x=tree[x].s[v>tree[x].v];//同find操作
	if(x) tree[x].cnt++;//x的权值等于v,已存在
	else//x不存在，把x的权值改为v并建立父子关系 
	{
		x=++idx;
		tree[p].s[v>tree[p].v]=x;
		tree[x].init(p,v); 
	}
	splay(x,0);
}
//查询数值为v的节点的排名
int get_rank(int v)
{
	//v不存在的特殊情况，不能直接find，先插入一个权值为v的点 
	insert(v);
	//insert操作已经把该点转到根了 
	int res=tree[tree[root].s[0]].size;//左哨兵算一个点，不用加1
	del(v);
	return res; 
 } 
//查询排名为k的数值 
int get_val(int k)
{
	int x=root;
	while(1)
	{
		int y=tree[x].s[0];
		if(tree[y].size+tree[x].cnt<k) 
			k-=tree[y].size+tree[x].cnt,x=tree[x].s[1];
		else if(tree[y].size>=k)
			x=tree[x].s[0];
		else break;
	}
	splay(x,0);
	return tree[x].v; 
}
int main()
{
	insert(-1e9),insert(1e9); //哨兵
	scanf("%d",&m);
	while(m--)
	{
		int op,x;
		scanf("%d%d",&op,&x);
		if(op==1) insert(x);
		if(op==2) del(x);
		if(op==3) printf("%d\n",get_rank(x));
		if(op==4) printf("%d\n",get_val(x+1));//左哨兵要多算一个
		if(op==5) printf("%d\n",tree[get_pre(x)].v);
		if(op==6) printf("%d\n",tree[get_suf(x)].v); 
	}
	return 0;
}