更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19525640

大意

这个题要求输出字典序最小的等价的二叉查找树。

思路

首先考虑这个题目，插入键值之后的树，是按照权值与时间来说的，我们将其设为二元组 $(k, t)$，那么我们不难发现这个树是一颗 Treap，权值满足 BST，时间戳满足小根堆。

对于样例，我们可以建出来这样的树：

$(1, 1), (4, 2), (3, 3), (2, 4)$

那么显然 $2$ 和 $4$ 是叶子节点，我们如果要保持这个 Treap 的结构的话，我们如果交换这俩节点的时间戳是没有问题的。

所以对于这种二维结构的维护，那我们可以用笛卡尔树维护，因为笛卡尔树也是一个 Treap，我们按照节点从左到右，时间戳为权值建立笛卡尔树。

那么我们建出来的树，显然是在一个节点有两个子节点的时候，那就是先左再右最优，且父更优。

则我们的有限度为：

$$父节点 \ge 左子节点 \ge 右子节点$$

那不就是一个先序遍历过程嘛。

也就是我们只需要建出一颗笛卡尔树，就直接先序遍历即可。