笛卡尔树是一种二叉搜索树，同时也满足大根堆或小根堆的性质，Treap也是一种笛卡尔树。
每个节点记录信息(x,y)，对于x是二叉搜索树，对于y是小根堆，在x递增的情况下，可以线性时间内构造一颗笛卡尔树。
两个点的lca的权值就是它们在原序列中的RMQ.
笛卡尔树的先序遍历即是原序列，对于下标为数组下标，键值为数组数组元素时，笛卡尔树的子树下标是一段连续的区间。
当x递增时，新插入的点只能是前面点的右儿子，前面点只能是它的左二子。如果有比它小的点，则该点作为第一个比它小的点的右儿子插入，如果有比它大的点，则最后一个比它大的点作为左儿子。一颗树的右链是从根出发一直往右儿子方向走的能够到达的所有点按照深度从浅到深排序后形成的链，单调栈中元素即为右链，最后栈中第一个元素即为根节点。
for(int i=1;i<=n;i++){
p=top;
while(p&&a[s[p]]>a[i])lc[i]=s[p--];
if(p)rc[s[p]]=i;
s[top=++p]=i;
}
给定一个长n的序列a，构造一个序列b，满足任意的l,r使得RMQ(a,l,r)=RMQ=(b,l,r)，b的数为[0,1]的实数，b的重量为b的元素和，问b的期望重量。笛卡尔树同构问题，设a的笛卡尔树字数大小为sz[x]，则b与a同构的概率为pai(i=1->n)(1/sz[i])，b中的数均匀分布，每个位置期望值为(0+1)/2=1/2，b的总重量和为n/2，所以b的期望重量为pai(i=1->n)(n/(2*sz[i]))。
void dfs(int x){
if(!x)return;
dfs(lc[x]),dfs(rc[x]);
sz[x]=sz[lc[x]]+sz[rc[x]]+1;
}
for(int i=1;i<=n;i++){
int p=top;
while(p&&a[s[p]]<a[i])lc[i]=s[p--];
if(p)rc[s[p]]=i;
if(p<top)lc[i]=s[p+1];
s[top=++p]=i;
}
dfs(s[1]);
ll ans=n*inv[2]%mod;
for(int i=1;i<=n;i++)ans=ans*inv[sz[i]]%mod;
由众多矩形组成的不规则图形，给出每个点的高度，问在其中放k个车且不互相攻击的方案数。建立高度的小根笛卡尔树，将矩形横向划分，一个矩形被编号为x当且仅当min{h[i]}=h[x]，对于一个父节点，儿子只会影响一些列不能选，只需该节点选代表矩阵的高度以内的列，并让儿子和节点内部的列没有冲突即可。
/*
假设在n*m的矩形选k个不攻击，那么方案数为C(n,k)*C(m,k)*k!
划分矩形，按照高度满足小根堆，由于下标连续，所以矩形的长度即为节点的size，高度为h[i]-h[fai]
在i的儿子选x个列时，留给当前节点有size-x个列可选
选y个的方案数为C(size-x,y)*C(h[i]-h[fa],y)*y!
f[i][j]为在i的子树中选j个的方案
f[i][j]=sum(l+r<=j)(f[lc][l]*f[rc][r]*C(size-(l+r),j-l-r)*C(h[i]-h[fa],j-l-r)*(j-l-r)!)
提取j-l-r进行计算
*/
void dfs(int x,int dep){
if(!x)return;
dfs(lc[x],a[x]),dfs(rc[x],a[x]);
int h=a[x]-dep;
sz[x]=sz[lc[x]]+sz[rc[x]]+1;
for(int i=0;i<=sz[x];i++)g[i]=0;
for(int i=0;i<=sz[lc[x]];i++)for(int j=0;j<=sz[rc[x]];j++)g[i+j]=(g[i+j]+f[lc[x]][i]*f[rc[x]][j]%mod)%mod;/*预处理f[lc][l]*f[rc][r]*/
for(int i=0;i<=sz[x];i++)for(int j=0;j<=i;j++)f[x][i]=(f[x][i]+g[i-j]*fac[j]/*上式(j-l-r)!*/%mod*C(h,j)%mod*C(sz[x]-(i-j),j)/*上式C(size-(l+r),j-i-l)*/%mod)%mod;
}
f[0][0]=1;
dfs(s[1],0);
cout<<f[s[1]][k];