BZOJ 3224: Tyvj 1728 普通平衡树

正文索引 [隐藏]

Description

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
1. 插入x数
2. 删除x数(若有多个相同的数,因只删除一个)
3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x,且最大的数)
6. 求x的后继(后继定义为大于x,且最小的数)

Input

第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数,表示对应答案

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

HINT

1.n的数据范围:n<=100000
2.每个数的数据范围:[-1e7,1e7]

题解

一个平衡树模版题、、Orz我手残复制了多项式忘记改符号了、对拍拍得我都要死了……
一棵treap是一棵修改了结点顺序的二叉查找树,如图,显示一个例子,通常树内的每个结点x都有一个关键字值key[x],另外,还要为结点分配priority[x],它是一个独立选取的随机数。
假设所有的优先级是不同的,所有的关键字也是不同的。treap的结点排列成让关键字遵循二叉查找树性质,并且优先级遵循最小堆顺序性质:
1.如果v是u的左孩子,则key[v] < key[u].
2.如果v是u的右孩子,则key[v] > key[u].
3.如果v是u的孩子,则priority[u] > priority[u].
这两个性质的结合就是为什么这种树被称为“treap”的原因,因为它同时具有二叉查找树和堆的特征。

用以下方式考虑treap会有帮助。假设插入关联关键字的结点x1,x2,…,xn到一棵treap内。结果的treap是将这些结点以它们的优先级(随机选取)的顺序插入一棵正常的二叉查找树形成的,亦即priority[xi] < priority[xj]表示xi在xj之前被插入。
在算法导论的12.4节中,其证明了随机构造的二叉查找树的期望高度为O(lgn),因而treap的期望高度亦是O(lgn)。
treap插入操作:
1.按照二叉树的插入方法,将结点插入到树中
2.根据堆的性质(我们这里为最小堆)和优先级的大小调整结点位置。
treap删除操作:
1.找到相应的结点
2.若该结点为叶子结点,则直接删除;
若该结点为只包含一个叶子结点的结点,则将其叶子结点赋值给它;
若该结点为其他情况下的节点,则进行相应的旋转,直到该结点为上述情况之一,然后进行删除。
旋转主要涉及到右旋转的左旋转,下面把右旋转的图画在下面:

代码