笛卡尔树学习笔记

1.介绍

笛卡尔树是一种树，每个节点都有两个关键字 $(k,w)$，其中如果按 $k$ 看，这棵树是满足二叉搜索树的，而按 $w$ 看，满足堆性质。

一半以数组下标为 $k$，数组元素为 $w$ 来建树。

2.流程

我们可以用栈来实现这一过程。

首先，由于是以下标作为 $k$ 的，所以我们在添加节点的时候一定是添加最右边节点的右子树的。

我们用栈来维护最右边这一条链，那么每次新加进来一个数都分几种情况。

栈顶元素大于当前值，那么我为了满足堆的性质，我们应该退栈，并往他的祖先继续看。

知道栈为空或者找到了比他小的节点，就让当前点的右儿子设为新加入的点，然后为了让下标满足堆的性质，就把这一轮最后一个退栈的子树设为新节点的右儿子。

然后就完成算法流程了。

代码

for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		int k=top;
		while(k>0 && a[stk[k]]>a[i]) k--;
		if(k) r[stk[k]]=i;
		if(k<top) l[i]=stk[k+1];
		stk[++k]=i;
		top=k;
	}