①排序之后直接构造笛卡尔树的方法:

首先将节点序列按照key从小到大排序，然后按照顺序插入节点，注意到排序之后，插入的节点的key值一定是树中最大的，所以只需查找最右端的路径，找到一个节点A的value大于待插入节点的value,同时A->right的value小于待插入节点的value。找到之后，只需将A的right指向待插入的节点，A的right原来指向的节点赋值给待插入节点的left指针。注意到查找最右路径的方向，如果从下到上查找，复杂度比较容易分析O(N)(因为查找过的节点必然会旋转到某个节点的左子节点，因此每个查找过的节点只会被查找一次)，如果从上倒下，比较复杂(和最右端的最终的路径长度有关吧)，会超过N，甚至更高，可能为O(N^2)。

②利用排序加左旋的方法:

就是一样先排序，然后使用treap插入节点，可以发现，所有的旋转都为左旋。这种方法也TLE了，这种方法有一个很重要的意义，就是分析了上个方法中从上到下扫描的复杂度。因为这两种方法的效率是等价的，都TLE。

我们将要将A的元素依次插入笛卡尔树C。每次插入都可能使树的形态发生变化。为了在O(N)的时间内完成整个插入过程，考虑C的右链，即根结点、根结点的右儿子、根结点的右儿子的右儿子……组成的链。注意这些元素的下标和值都是递增的。下标最大，即将要插入的元素A一定是新树右链的最后一个元素。原来的右链中，值比A大的元素在新树中不再属于右链，这些元素组成的链成为A的左子树的右链;原来右链中的其它元素加上A组成了新的右链。初看起来，寻找分界点的最佳方法是O(logN)时间的二分查找;但是对于整个过程来说，O(NlogN)的时间复杂度不是最优的。关键在于一旦一个元素比A大，它就从右链中被永久地移除了。如果按照从后到前的顺序判断一个元素是否大于A，则每次插入的时间复杂度为O(k+1)，k为本次插入中移除的右链元素个数。因为每个元素最多进出右链各一次，所以整个过程的时间复杂度为O(N)。

用一个栈结构维护右链元素的下标，上述过程可以很容易地实现。(见下面代码部分)