笛卡尔树总结

笛卡尔树的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]树的序

对于给定的生成序列，建立笛卡尔树，然后先序遍历输出即可！
代码