笛卡尔树的key值满足二叉搜索树，value满足小根堆
线性构造尝试：按照key从小到大排序，维护最右链的单调栈，每次从底开始从上比较，找到一个比当前加入点的value小的点v为之，把v的右儿子挂在自己的左侧，并把当前点加入最右链
P5854 【模板】笛卡尔树
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e7+5;
int n,a[maxn],s[maxn],tail,l[maxn],r[maxn];
inline int read()
{
char cc=getchar();
register int x=0,f=1;
while((cc<'0' || cc>'9') && cc!='-') cc=getchar();
if(cc=='-') f=-1,cc=getchar();
while(cc>='0' && cc<='9') x=x*10+cc-'0',cc=getchar();
return f*x;
}
signed main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
n=read();
for(register int i=1;i<=n;i++) a[i]=read();
s[++tail]=0;
for(register int i=1;i<=n;i++)
{
while(tail && a[i]<a[s[tail]]) l[i]=s[tail--];
if(tail) r[s[tail]]=i;
s[++tail]=i;
}
int ans1=0,ans2=0;
for(register int i=1;i<=n;i++)
{
ans1^=i*(l[i]+1);
ans2^=i*(r[i]+1);
}
printf("%lld %lld",ans1,ans2);
return 0;
}
P1377 [TJOI2011]树的序
对于给定的生成序列，建立笛卡尔树，然后先序遍历输出即可！
代码
