笛卡尔树性质：
每个结点存储 (k,w) ，即一个序偶
-
对于k而言，是一个二叉搜索树（满足条件：根节点大于左节点，小于右节点）
-
对于w而言，是一个小根堆/大根堆（满足条件：根节点值小于/大于左，右节点值）
笛卡尔树不是平衡的
笛卡尔树的构建：
如何使一个数组->笛卡尔树？
单调栈O（n），处理出每一个结点的左儿子，右儿子，权值w
举例：对于上图的数组 a=[9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5]，构建一颗小根堆笛卡尔树
显然序偶 (k,w) = (元素下标，元素大小）
我们使单调栈元素是单调递增的
从左至右：显然元素下标是单调增的，所以为了满足二叉搜索树的条件，我们首先会把这个结点视为右结点（因为前面元素下标都比该结点小）
然后通过 维护的单调栈 判断这个结点是哪一个结点的右结点
-
如果单调栈为空，那么该结点是初始结点，不用判断左右结点情况
-
如果单调栈非空：
若栈顶元素大小大于该元素大小，由于我们需要维护小根堆，显然当前结点不能是栈顶结点的儿子。直接出栈
若栈顶元素大小小于该元素大小，那么我们直接把当前结点看作栈顶结点的右结点
同时，我们需要维护出栈的最后一个元素结点，我们将该元素结点看作当前结点的左结点（元素大小既大于当前结点，元素下标又小于当前结点）
特别的，如果不断出栈，最后栈为空，说明当前结点看作根结点
最后将当前结点入栈
参考代码
struct node{int l=0,r=0,fa=0;int val;
};int n;cin>>n;vector<int>a(n+1);rep(i,1,n)cin>>a[i];vector<node>tr(n+1);stack<int>stk;rep(i,1,n){int L=0,R=0;while(stk.size()&&a[stk.top()]>a[i]){L=stk.top();stk.pop();}if(L!=0){tr[L].fa=i;if(stk.size())tr[stk.top()].r=i;}else if(stk.size()){tr[stk.top()].r=i;}stk.push(i);tr[i].val=a[i];tr[i].l=L;tr[i].r=R;}