1.定义
笛卡尔树是一种特殊的二叉树，同时满足小根堆和二叉搜索树的性质，笛卡尔树的每个节点有两个值（k,w），k满足二叉搜索树性质，w满足小根堆性质。Treap也是一种笛卡尔树
2.性质
-
如果k,w是分别两两不同的，那么笛卡尔树也是唯一的
-
对于一颗笛卡尔树，它的中序遍历是原序列a
-
在原序列中的区间[l,r]的最小值,是l,r的最近公共祖先
3.建树
3.1.栈构建
先将元素按键值k排序，再依次插入笛卡尔树中，那么每次我们插入的元素必然在这个树的右链（右链：即从根结点一直往右子树走，经过的结点形成的链）的末端，然后从下往上比较右链节点x与当前节点u的w，若找到某个节点满足\(u_w>x_w\)，则把u接到x的右儿子上，而x原本的右子树就变成u的左子树
显然，每个点最多进出右链1次，所以可用栈维护，时间复杂度O（n）
3.2.代码
例题：【模板】笛卡尔树
https://www.luogu.com.cn/problem/P5854
#include<cstdio>
#define ll long long
using namespace std;
int n,a[10000007],s[10000007],ls[10000007],rs[10000007],top;
ll ans1,ans2;
void build()
{
for(int i=1;i<=n;i++)
{
int k=top;
while(k&&a[s[k]]>a[i]) k--;
// printf("%d %d\n",top,k);
if(k) rs[s[k]]=i;
if(k<top) ls[i]=s[k+1];
s[++k]=i;
top=k;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build();
for(int i=1;i<=n;i++)
{
ll x=1ll*i*(ls[i]+1),y=1ll*i*(rs[i]+1);
ans1^=x,ans2^=y;
// printf("%d %d\n",ls[i],rs[i]);
}
printf("%lld %lld",ans1,ans2);
return 0;
}