笛卡尔树

笛卡尔树是一棵二叉树，每个节点的编号满足二叉搜索树的性质，即二叉树的中序遍历是原数列，每个节点的权值满足堆的性质，也就是说，(Treap)就是笛卡尔树

在笛卡尔树上两个点的(LCA)就是这一区间的最值

用增量法来建树，维护一个单调栈，栈内元素为右子树链

因为每个节点最多进栈出栈一次，所以时间复杂度是(O(n))的

若不是序列，则是考虑二元组((a,b))，(a)满足二叉搜索树的性质，(b)满足堆的性质

建树前先以(a)为关键字排序

笛卡尔树本质为单调栈的另一种形式，所以可以用来解决最大子矩形问题

(code:)

void build()
{
    for(int i=1;i<=n;++i)
    {
        while(top&&a[st[top]]>a[i]) ls[i]=st[top--];
        if(top) rs[st[top]]=i;
        st[++top]=i;
    }
}