ask_pre

前驱：小于中最大的。

向右走说明当前节点小，可能是前驱；向右走说明比当前节点大，不可能是前驱。

可能是前驱的中最大的即为前驱。

int ask_pre(int i,int key)
{
	if(i==0)return -2147483647;
	if(tre[i].val>key)return ask_pre(tre[i].lc,key);
	else return max(tre[i].val,ask_pre(tre[i].rc,key));
}

ask_nex

后继：大于中最小的。

和前驱差不多，只是左右相反，且求最小。

int ask_nex(int i,int key)
{
	if(i==0)return 2147483647;
	if(tre[i].val>key)return ask_nex(tre[i].rc,key);
	else return min(tre[i].val,ask_nex(tre[i].lc,key));
}

复杂度分析

期望复杂度：\(O(n\log n)\)。

最差复杂度：\(O(n^2)\)。

因为如果插入的序列是单调的，会使我们的 BST 退化成一条链，单次复杂度 \(O(n)\)，因此需要平衡操作。

平衡树

旋转平衡树

Treap

Treap=Tree+Heap

Tree 指的就是上述 BST，而 Heap 指堆。

所以 Treap 的中文翻译就是树堆。

堆

堆，一种完全二叉树。这不就避免退化成链了吗

堆有大根堆和小根堆，不过由于 STL 的原因，C++ 中很少有人手打堆，而是直接用 priority_queue，这就导致了有些人只知道堆，但不了解它的工作原理。

priority_queue 支持的操作有：插入（push），查询最值（top），弹出最值（pop）。堆还支持删除任意数（remove），不过不常用。

堆的主要操作有两个：上浮 和 下沉。具体实现方式，前两篇题解讲的还是挺好的。

rotate

从性质来看，树和堆是两个矛盾的数据结构。

不过，我们引入堆是利用它是一个完全二叉树来防止退化成链，所以整棵树还是一棵 BST。

所以我们给 Treap 的每个节点赋上随机值 heap，让 val 满足 BST 性质，heap 满足堆性质。

就像这样（图片来源于 洛谷日报）

所以要如何在插入节点后使 heap 满足堆性质呢？

旋转（rotation）。

那么，如何旋转呢？

显然，这样是不行的，因为 651 变成三叉了……

但经过观察可以发现，原来 37 既有左儿子又有右儿子，但这样旋转之后，就只剩下左儿子了。而且，433 若成为 37 的的右儿子并不破坏 Treap 的 BST 性质。

所以应该这样转：

这是巧合吗？

看一下一般情况：

按上述转法，转完之后就是：

（小写字母表示节点，大写字母表示子树）

对于上边的图的中序遍历是 CfAsB，下边的图中序遍历也是 CfAsB，可见旋转并没有破坏 BST 性质。

所以这样转是正确的，这就是左旋。

有左旋，就有右旋。就像这样：

左旋 f= 右旋 s

再以左旋为例，看一下相对关系：

• s 是 f 的右儿子
• f 的左儿子不变；
• s 的右儿子不变；
• f 的右儿子变为 s 的左儿子；
• s 的左儿子变为 f；

那么代码就是这样的：

void pushup(int i)
{
	tre[i].siz=tre[tre[i].lc].siz+tre[tre[i].rc].siz+1;
}
void zig(int &i)//左旋
{
	int s=tre[i].rc;
	tre[i].rc=tre[s].lc;
	tre[s].lc=i;
	pushup(i);pushup(s);
	i=s;
}
void zag(int &i)//右旋
{
	int s=tre[i].lc;
	tre[i].lc=tre[s].rc;
	tre[s].rc=i;
	pushup(i);pushup(s);
	i=s;
}

当然，用 \(son_0\) 表示左儿子，\(son_1\) 表示右儿子，旋转操作还可以合并成：

void pushup(int i)
{
	tre[i].siz=tre[tre[i].lc].siz+tre[tre[i].rc].siz+1;
}
void rotate(int &i,int t)
{
	int s=tre[i].son[t^1];
	tre[i].son[t^1]=tre[s].son[t];
	tre[s].son[t]=i;
	pushup(i);pushup(s);
	i=s;
}

了解如何旋转之后，那么什么时候进行旋转操作呢？

在插入节点的时候，节点根据 BST 性质找到合适的位置；插入完成后，再比较当前节点和左右子节点的 heap，不满足堆性质的就旋转。

此处的堆性质可以是大根堆，也可以是小根堆。

void insert(int &i,int key)
{
	if(i==0)
	{
		i=++cnt;tre[i].heap=rand();
		tre[i].siz=1;tre[i].val=key;
		return;
	}
	tre[i].siz++;
	if(key>tre[i].val)
	{
		insert(tre[i].rc,key);
		if(tre[tre[i].rc].heap

void remove(int &i,int key)
{
	if(tre[i].val==key)
	{
		if(tre[i].lc==0||tre[i].rc==0)
		{
			i=tre[i].lc+tre[i].rc;
			return;
		}
		if(tre[tre[i].lc].heap

#include
#include
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr1(int s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr1(s/10);
	putchar(s%10+48);
}
void wr(int s){wr1(s),putchar('\n');}
const int inf=1e5+7;
int n,root,op,x,cnt;
struct Treap{
	int val,heap;
	int siz,son[2];
	#define lc(i) tre[i].son[0]
	#define rc(i) tre[i].son[1]
}tre[inf];
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return atre[i].val)
	{
		insert(rc(i),k);
		if(tre[rc(i)].heap=k)return ask_pre(lc(i),k);
	return max(tre[i].val,ask_pre(rc(i),k));
}
int ask_nex(int i,int k)
{
	if(i==0)return 2147483647;
	if(tre[i].val<=k)return ask_nex(rc(i),k);
	return min(tre[i].val,ask_nex(lc(i),k));
}
int main()
{
	n=re();
	for(int i=1;i<=n;i++)
	{
		op=re();x=re();
		if(op==1)insert(root,x);
		if(op==2)remove(root,x);
		if(op==3)wr(ask_rank(root,x));
		if(op==4)wr(ask_kth(root,x));
		if(op==5)wr(ask_pre(root,x));
		if(op==6)wr(ask_nex(root,x));
	}
	return 0;
}