← 返回题目列表

AtCoder · utpc2011_10

J. 随机平衡二叉搜索树

中文机器翻译题面 查看原题
我们收到报告称此问题评分不正确。

顺便说一下,据说在 G○○gle Code Jam 地区赛上坐在右边座位的男人的 ID 是 rng_58。 我记得在东京大学时期,有个类似 ID 的同伴,但我的同伴一个都不缺都是美少女。 我感觉她好像是那种所谓的无表情神秘系角色。

也就是说,他是个不认识的男人。rng 是什么缩写呢? 大概是 Random Number Generator(随机数生成器)没错。 他应该擅长使用随机化算法吧。

顺便说一下,使用随机数的平衡二叉搜索树 Treap, 在 2011 年左右的编程竞赛中似乎经常被使用, 但到了 20XX 年的现在,已经不太使用了。

当时 Treap 因为实现简单而与 Splay 树和 Scapegoat 树一起被广泛使用。 进入 20XX 年,在这个每天都会举行拼命的程序设计竞赛的世界里, 光凭实现稍微简单一些的这种理由是绝不可能被采纳的。 每个人都在考虑让程序尽可能更快, 而成为世界大赛选手的话,能够在十几秒内写出 Left-leaning 红黑树也是理所当然的。

例如,Treap 比红黑树慢的原因,据说是因为高度的常数倍起了作用。 在这里,让我们冷静地将其数值化地考察,从而恢复内心的平静。

問題

将键值设为实数的 Treap N 插入 n 个随机元素时, 高度为 h (h = 0, 1, …, N - 1) 的概率是多少。 下面,将做更详细的说明。

Treap 是一种使用随机数的平衡二叉搜索树。 每个节点除了有键外,还有一个叫做优先度的值。 这里,键和优先度都是 0 减去 1 以内的实数值。 在 Treap 中,以下两个条件总是保持的。

  1. 关于键的条件
  • 对于每个节点,其左子节点及其以下的节点具有比自己小的键
  • 对于每个节点,其右子节点及其以下的节点具有比自己大的键
  1. 关于优先度的条件
  • 对于每个节点,其子节点具有比自己小的优先度

下图是 Treap 的一个例子。 每个节点的上方写着键,下方写着优先度。

//img.atcoder.jp/utpc2011/treap_fig1.png

由 7 个节点组成的 Treap 例子。

插入操作如下进行。 插入的键为 x 。 删除

  1. 插入的新节点的优先级 p 该值应乘以 0 减去 1 从到 的均匀分布中随机决定。
  2. 与普通二叉搜索树相同,首先忽略优先级插入新节点。
  3. 重复必要次数的旋转操作,使新节点满足优先级条件并向上提升。

关于树的旋转操作,已在附录章节中详细描述,请参考。

下图是刚才例子中插入一个键为 0.5、优先级为 0.7 的顶点的过程示例。

//img.atcoder.jp/utpc2011/treap_fig2.png

首先忽略优先级,节点被插入。

//img.atcoder.jp/utpc2011/treap_fig3.png

进行旋转,新节点升到上方。

//img.atcoder.jp/utpc2011/treap_fig4.png

再次进行旋转,由于满足优先级条件,插入结束。

对空的 Treap N 添加若干键, 还是 0 减去 1 以内的均匀分布随机选择并插入。 最终高度为 h 的概率, 请对每个 h = 0, 1, …, N - 1 求出。 此外,假设实数可以以足够的精度处理, 例如两个节点的优先级相等的概率可以视为 0。 另外,高度是从根节点到各节点必须经过的边的最大数量。

入力

个整数的一行 N 被写了。

出力

输出是 由 N 行组成。 第 i 行输出高度为 i - 1 的概率。 数值小数点后显示位数不限。

制約

  • 1 ≤ N ≤ 3 × 104
  • 要输出的值为 打印除以 10 - 5 以下的误差也可以包含在内。

入出力例

入力例 1:

1

输入示例 1 的输出示例:

1.0

入力例 2:

2

输入示例 2 的输出示例:

0.0000000000
1.0000000000

補足

树的旋转操作有右旋和左旋。右旋是将下面两个图中的第一个状态变为第二个状态的操作,左旋是将下面两个图中的第二个状态变为第一个状态的操作。

//img.atcoder.jp/utpc2011/treap_fig_rot1.png

右旋之前,或者左旋之后

//img.atcoder.jp/utpc2011/treap_fig_rot2.png

右旋之后,或者左旋之前

在 Treap 中,如果要提升的节点是其父节点的左子节点,就对要提升的节点应用如图中将其变为 P 的右旋;如果要提升的节点是其父节点的右子节点,就应用如图中将其变为 Q 的左旋。

想了解更多关于树的旋转操作的内容,请参考例如以下内容。

关于 Treap,想了解更多信息,可以参考例如以下内容。