| 题目名称 | 2840. 二叉查找树 |
|---|---|
| 输入输出 | bst.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 13 |
| 题目来源 |
 Hyoi_0Koto
于2017-10-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：13， 提交：32， 通过率：40.63% | ||||
 FoolMike |
100 | 0.519 s | 6.54 MiB | C++ |
 Regnig Etalsnart |
100 | 0.550 s | 4.15 MiB | C++ |
 Menamovic |
100 | 0.559 s | 3.59 MiB | C++ |
|
Regnig Etalsnart |
100 | 0.654 s | 8.30 MiB | C++ |
 hyghb |
100 | 0.704 s | 4.87 MiB | C++ |
 胖周zzf |
100 | 1.119 s | 8.32 MiB | C++ |
 Fisher. |
100 | 1.255 s | 6.04 MiB | C++ |
 Tanya |
100 | 1.297 s | 8.32 MiB | C++ |
 Hyoi_0Koto |
100 | 1.351 s | 7.18 MiB | C++ |
 liuyu |
100 | 1.458 s | 48.38 MiB | C++ |
| 关于 二叉查找树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
如果以随机顺序插入，以初始插入时间为fix维护treap不应该快么...
hyghb
2018-01-07 16:48
6楼
| ||||
|
新姿势 笛卡尔树
hyghb
2018-01-07 16:05
5楼
| ||||
|
叫你开了longlong%d
 Ostmbh
2017-10-10 09:09
4楼
| ||||
|
就两个线段树？其他人的看不懂...
| ||||
|
为什么最近的出题人这么喜欢笛卡尔树……
| ||||
|
一开始就写出来了50分递归，怕爆栈又改成了循环，结果又成0分了，懊悔......
| ||||
【题目描述】
二叉查找树是一种特殊的二叉树（每个节点最多只有两个儿子的树）。树的每个节点上存有一个唯一的值，并且满足：这个节点的左子树内所有点的值都比这个节点的值小，且右子树内所有点的值都比这个节点的值要大。
对于一棵二叉查找树T，我们可以将一个值为 x的新点插入 T中，且保持树的性质。算法如下：
需要将 x 插入树 T时，执行 insert(x,T.root)。
现在有 N 个数需要插入一棵空树中。给定插入序列，请在每个元素被插入之后，输出所有节点的深度总和（根的深度为 0）。
【输入格式】
输入的第一行一个整数 n，表示序列长度。
接下来一行n个数是序列中的数字，这些数字是各不相同的，在[1, n]区间。
【输出格式】
输出 n 行，第 i 行整数表示第 i个数插入树后，至这个节点的节点深度总和。
【样例输入】
8 3 5 1 6 8 7 2 4
【样例输出】
0 1 2 4 7 11 13 15
【数据规模与约定】
对于 50%的数据，满足n ≤ 1000
对于100%的数据，满足n ≤ 3 ∗ 1e5
【来源】
qbxt 2017.10.7 t1