【数据结构】笛卡尔树

把一个数组的元素，从左到右插入笛卡尔树，可以用栈O(n)地构建出来。笛卡尔树上的节点满足堆的性质（小根堆就是一个节点小于其两个子节点的权值）。所以用这个方式扫描出的笛卡尔树，一棵子树就是对应一段连续的区间，而子树的根节点就是这段区间的最值（小根堆就是最小值）。

以最大矩形面积的小根堆为例：

从根节点一直往右走，形成的链称为右链。

从下往上逐个检查右链上的节点，找到第一个比当前节点u的权值小的点x，在那之前的点都直接忽视掉。

由于点x的权值比u小，所以u就要作为x的其中一个子节点，这里就让它做x的右节点，成为新的右链的末端。而之前被忽略掉的点，就作为u的左子树。相当于就是：

1. 把右链逐个弹出，把最后一个点y（如果存在）完整的整棵树取下来，直到右链的第一个点x小于u
2. u接在x的右子树，这样堆的性质满足
3. 取出的子树接在u的左子树，堆的性质满足
4. 相当于就是u终结了被取出子树的根节点y的右延展性，被u节点掐断了，这是因为u比y小，阻断了y

static const int MAXN = 200000 + 10;

int h[MAXN];

int rt;
int lc[MAXN];
int rc[MAXN];

void build (int n) {
    static int stk[MAXN];
    memset (stk, 0, sizeof (lc[0]) * (n + 1));
    memset (lc, 0, sizeof (lc[0]) * (n + 1));
    memset (rc, 0, sizeof (lc[0]) * (n + 1));
    for (int i = 1, top = 0; i <= n; i++) {
        int k = top;
        while (k >= 1 && h[stk[k]] > h[i]) {
            k--;
        }
        if (k >= 1) {
            // 节点i的权值>=栈顶节点的权值，挂在栈顶节点的右子树下
            rc[stk[k]] = i;
        }
        if (k + 1 <= top) {
            // 栈顶节点原本的右子树权值>节点i的权值，改为挂在节点i的左子树下
            lc[i] = stk[k + 1];
        }
        stk[++k] = i;
        top = k;
    }
    rt = stk[1];    // 笛卡尔树的根
}

如果树里面有重复的元素，会怎么样呢？上面的这个实现中，会统统挂在最先进入笛卡尔树（最左边）的重复元素下面。其实是不影响的。

构造出笛卡尔树后，可以用一次简单的深搜算出答案。树的size是否可以在构建时就算出来呢？其实是可以的，元素出栈（离开右链）之后就不会动到其中的子树了，这个区间就固定下来了。需要做的其实就是不断pop栈把size更新一下。然后对于计算最大矩形面积，也可以顺便更新答案。

但是搞得太不直观了，不利于扩展，直接用dfs就好。dfs的话就不用维护多一个size，直接return就行。

ll ans = 0;

int dfs (int u) {
    if (u == 0) {
        return 0;
    }
    int siz = dfs (lc[u]) + 1 + dfs (rc[u]);
    ans = max (ans, 1LL * siz * h[u]);
    return siz;
}

比起两次扫描单调栈才能确定边界，也有很多+1-1的问题，这个算法算是非常简单了。额外的空间其实也没有多用多少，反正都是O(n)。