「BZOJ3224」JoyOI 1728 普通平衡树

2014年8月23日22,6945

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还是很不错的,用来写暴力没准出奇迹呢?

 

avatar
5 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
6 Comment authors
DaCongyoooshinow蒟蒻HJNXAShzwer Recent comment authors
  Subscribe  
提醒
DaCong

” 3.如果v是u的孩子,则rand[u] > rand[u].”
这里是不是说错了?应该是 rand[u]> rand[v] 吧。

yoooshinow
yoooshinow

请问一下…平衡树插入结点那里,如果是放到左孩子的话,为什么是左孩子的rnd小于这个点的rnd才右旋…感觉应该是大于…

HJNXAS
HJNXAS

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

蒟蒻
蒟蒻

旋转时赋的?

xxx
xxx

set 如果要重载字符 要重载哪个?