| 题目名称 | 2421. [HZOI 2016] 简单的Treap |
|---|---|
| 输入输出 | treap.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Hzoi_
于2016-08-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：62， 提交：231， 通过率：26.84% | ||||
 AAAAAAAAAA |
100 | 0.667 s | 9.88 MiB | C++ |
 Hzoi_Maple |
100 | 0.773 s | 5.56 MiB | C++ |
 rewine |
100 | 0.785 s | 8.38 MiB | C++ |
 Cooook |
100 | 0.786 s | 5.43 MiB | C++ |
 AntiLeaf |
100 | 0.813 s | 8.38 MiB | C++ |
 Narcissus |
100 | 0.832 s | 8.87 MiB | C++ |
 hinanawi |
100 | 0.869 s | 11.28 MiB | C++ |
 HZOI_蒟蒻一只 |
100 | 0.895 s | 9.85 MiB | C++ |
|
AntiLeaf |
100 | 0.897 s | 9.83 MiB | C++ |
 WildRage |
100 | 0.917 s | 6.03 MiB | C++ |
| 关于 简单的Treap 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
笛卡尔树。。。开O2跑到榜首
AAAAAAAAAA
2017-12-28 22:23
21楼
| ||||
|
T掉了
 Go灬Fire
2017-03-07 07:30
20楼
| ||||
|
建一颗treap直接dfs就好了
| ||||
|
写个treap练练手，发现treap真是短
| ||||
|
跑了跑发现自己代码挺挫，于是又丧尽天良加了个快读快写
用zkw卡了半天终于卡上榜首了......被自己感动的稀里哗啦...... | ||||
|
跑了跑发现自己代码挺快，于是又丧尽天良加了个快读快写
| ||||
|
回复 @liu_runda :
QAQ不带这么玩的 AntiLeaf
2016-08-08 16:37
15楼
| ||||
|
跑了跑发现自己代码挺快，于是又丧尽天良加了个快读
 liu_runda
2016-08-08 16:19
14楼
| ||||
 _Itachi
2016-08-08 06:36
13楼
| ||||
|
回复 @liu_runda :
本来就有几个链...... AntiLeaf
2016-08-08 06:32
12楼
| ||||
@@@@
FoolMike
NewBee【题目描述】
Treap是一种平衡二叉搜索树，除二叉搜索树的基本性质外，Treap还满足一个性质：
每个节点都有一个确定的优先级，且每个节点的优先级都比它的两个儿子小(即它的优先级满足堆性质)。
不难证明在节点的优先级都事先给定且互不相同时，对应的Treap有且仅有一个。
现在，给定n个数和每个数对应的优先级，求出对应的以数的大小作为二叉搜索树比较依据的Treap的先序遍历结果。
对先序遍历的定义是：先访问根节点，再访问左子树，最后访问右子树。
【输入格式】
第一行一个数n表示数的个数。
第二行n个数表示每个数的大小。
第三行n个数表示每个数对应的优先级。
【输出格式】
一行n个数，表示Treap的先序遍历结果(对于每个节点，输出对应的数)。
【样例输入】
7 2 11 5 9 1 4 3 2 10 1 8 4 6 5
【样例输出】
5 2 1 3 4 9 11
【样例解释】
对应的Treap如图所示，其中圈内的数是给出的数，圈外的数是节点的优先级。
【数据范围】
n<=500000。
所有的数和优先级都互不相同且在int(C++)/longint(Pascal)范围内。
【提示】
为了给不想用栈模拟递归的孩纸们偷懒的机会，C++选手请在main函数的开头加入以下代码：
int __size__=128<<20;
char *__p__=(char*)malloc(__size__)+__size__;
__asm__("movl %0, %%esp\n"::"r"(__p__));
注意上述代码会占用你128MB的空间，请自行调整代码。
【来源】
HZOI 2016