COGS2421 [HZOI 2016]简单的Treap 笛卡尔树

发布于 2017-07-26  2.96k 次阅读


[toggle hide="yes" title="题目" color=""]

【题目描述】

Treap是一种平衡二叉搜索树,除二叉搜索树的基本性质外,Treap还满足一个性质:

每个节点都有一个确定的优先级,且每个节点的优先级都比它的两个儿子小(即它的优先级满足堆性质)。

不难证明在节点的优先级都事先给定且互不相同时,对应的Treap有且仅有一个。

现在,给定n个数和每个数对应的优先级,求出对应的以数的大小作为二叉搜索树比较依据的Treap的先序遍历结果。

对先序遍历的定义是:先访问根节点,再访问左子树,最后访问右子树。

【输入格式】

第一行一个数n表示数的个数。

第二行n个数表示每个数的大小。

第三行n个数表示每个数对应的优先级。

【输出格式】

一行n个数,表示Treap的先序遍历结果(对于每个节点,输出对应的数)。

【样例输入】

【样例输出】

【样例解释】

对应的Treap如图所示,其中圈内的数是给出的数,圈外的数是节点的优先级。

【数据范围】

n<=500000。

所有的数和优先级都互不相同且在int(C++)/longint(Pascal)范围内。

【提示】

为了给不想用栈模拟递归的孩纸们偷懒的机会,C++选手请在main函数的开头加入以下代码:

注意上述代码会占用你128MB的空间,请自行调整代码。

【来源】

HZOI 2016

[/toggle]

笛卡尔树和Treap一样,维护平衡树和堆性质。当一个序列按照值(自身权值)有序有序时,按照序列相对位置建树即可得到二叉搜索树,同时,赋予其随机的优先级又可以维护其堆性质。

笛卡尔树的构造

设节点权值为v,优先级为r。这里对于 r 而言,我们构造小根堆。
我们将一个节点表示为:(v, r)。首先将所有节点按照 v 从小到大排序。
引入一个栈,维护了笛卡尔树最右边的一条链上面的元素。
从前往后遍历 

  1. 对于每一个,从栈中找出(从栈顶往栈底遍历)第一个小于等于ri的元素 rj
  2. 将 rj 之上即 r  的点全部弹出。
  3. 在树中,将 j 的右子树挂在  的左子树上,将  挂在原来  的右子树的位置。

用很不严谨的话说,就是一个节点 i 来了,我们只考虑在最右边的链插入这个节点。由于要维护堆性质,如果它的 r 比之前的都大,那么他就可以挂在最右边的链的最后一个,由于 v 从小到大,不违反二叉搜索树的性质。如果它比之前的某些小,那么找到小于等于它 r 的元素 j,变成它的右儿子,那么堆的性质满足了,又要满足二叉搜索树的性质,所以把原先 j 的右儿子挂在 i 的左子树。

 

模拟过程

我们用下面一张图来简要讲解一下build的构造过程(注意,定义r为维护堆性质的随机键值)

假设这是我的无旋treap目前的状态,我用一个栈来维护这棵树最右边的一条链,并且每一次在右下角处插入节点

假设我此时我们在9的右儿子添加了一个13,若13的r值小于栈顶元素9的r,那么就开始退栈,停止退栈的条件有两个,满足任意一个即停止:

1.当前栈顶元素r<13的r(约定r小的在上)
2.栈为空
若13的r>3的r并且<4的r,那么上图会变为:

上一个模板代码:

所以这道题就已经解决了。
[toggle hide="no" title="代码" color=""]

 

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974