笛卡尔树

定义：笛卡尔树是一种二叉树，每一个结点由一个键值二元组 \((k,w)\) 构成。要求 \(k\) 满足二叉搜索树的性质，而 \(w\) 满足堆的性质。一个有趣的事实是，如果笛卡尔树的 \((k,w)\) 键值确定、并且 \(k\) 不相同， \(w\) 不相同，那么这个笛卡尔树的结构是唯一的。

---

建树方法：

给定一个序列A，下面建树的过程中以小根堆为例，定义序列中第 \(i\) 个元素的键值为 \((i,A_i)\) ，也就是 \(i\) 对应 \(k\) ，\(A_i\) 对应 \(w\) ，我们要求 \(k\) 满足二叉搜索树的性质，那么此时我们进行思考，我们每插入一个新的点，由于 \(k\) 必然是递增关系，所以这个新点的 \(k\) 比上一个点大，这个时候我们能确定，这两个点的关系必然是 \(k-1\) 点是 \(k\) 点的左儿子或者 \(k\) 点是 \(k-1\) 点的右儿子，直接和上一次的点比较 \(w\) 即可，如果后来的 \(w\) 大，就直接成为前一个的右儿子，同时也和下面的右儿子比较一下，看看符不符合这个关系，不然的话，成为前一个的父亲，同时与上方的父亲进行比较，继续判断是否交换

我们发现，上述操作维护的都是原节点的右链，所以我们可以选择直接处理

实现方法：每个数只会进出右链一次，这个过程我们用栈维护，如果一个数不在右栈上的话就弹出，栈中维护当前笛卡尔树的右链上的结点，复杂度 \(O(n)\)

---

rep(i, 1, n){
    int k = top;
    while (k && h[stk[k]] > h[i]) k--;
    if (k) rs[stk[k]] = i;  // rs代表笛卡尔树每个节点的右儿子
    if (k < top) ls[i] = stk[k+1];  // ls代表笛卡尔树每个节点的左儿子
    stk[++k] = i;
    top = k;
}

新建一个大小为 n 的空栈。用 top 来标操作前的栈顶，k 来标记当前栈顶。
For i := 1 to n
    k := top
    While 栈非空 且 栈顶元素 > 当前元素 
        k--
    if 栈非空
        栈顶元素.右儿子 := 当前元素
    if k < top
        当前元素.左儿子 := 栈顶元素
    当前元素入栈
    top := k