【bzoj3224】Tyvj 1728 普通平衡树

2014年8月23日3,9525

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

题解

这是一道平衡树的模板题

treap是一棵修改了结点顺序的二叉查找树

通常树内的每个结点x都有一个关键字值key[x],另外,还要为结点分配一个随机数。

假设所有的优先级是不同的,所有的关键字也是不同的。treap的结点排列成让关键字遵循二叉查找树性质,并且优先级遵

循最小堆顺序性质:
1.如果v是u的左孩子,则key[v] < key[u].
2.如果v是u的右孩子,则key[v] > key[u].
3.如果v是u的孩子,则rand[u] > rand[u].
这两个性质的结合就是为什么这种树被称为“treap”的原因,因为它同时具有二叉查找树和heap的特征。

8.23:用vector可以AC,但vector的插入理论上是On的

实际测试发现,vector从头插入10W个数我的电脑只用了0.8s

倒数50亿用了12s,干脆我们把插入视为根号级别。。。

所以说,vector还是很不错的,用来写暴力没准出奇迹呢?

 

  1. 请问一下,黄学长,你的treap删除一个点时,当它两个儿子都不为空时,并没有把左儿子赋到它上面啊。。。。

  2. Pingback: Bzoj3224 Tyvj 1728 普通平衡树 – To strive to seek to find and not to yield