COGS2421 [HZOI 2016]简单的Treap 笛卡尔树 数据结构

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

笛卡尔树和Treap一样,维护平衡树和堆性质。当一个序列按照值(自身权值)有序有序时,按照序列相对位置建树即可得到二叉搜索树,同时,赋予其随机的优先级又可以维护其堆性质。 笛卡尔树的构造 设节点权值为v,优先级为r。这里对于 r 而言,我们构造小根堆。 我们将一个节点表示为:(v, r)。首先将所有···