笛卡尔树

定义

笛卡尔树一是一棵二叉树。对于每个结点，有两个权值 $k,w$。 若只看 $k$，整颗树为二叉查找树；只看 $w$，树为堆。

如图，点在数组中的位置号码为 $k$，元素内数字为 $w$。

性质

• 若每个 $k,w$ 均不相同，则笛卡尔树的形式是唯一的。

• 结点要么没有左儿子，要么左儿子没有左儿子。

建树

这里默认堆为小根堆。

用单调栈维护树的右链。

设新加入点 $u$，若栈中（即右链）所有 $w$ 值均大于 $w_u$，则栈底（即右链头即当前树根）变为 $u$ 左儿子。

若栈中第一个 $w$ 小于 $u$ 的点为 $v$，则 $v$ 的右儿子全部变为 $u$ 的左儿子，$u$ 成为 $v$ 的右儿子。

code

模板题 [P5854] 笛卡尔树

#include <bits/stdc++.h>
#define rei register int
#define N 10000010
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	x *= f;
}

int n, a[N], st[N], top, ls[N], rs[N];
ll ansl, ansr;

int main()
{
	read(n);
	for (rei i = 1; i <= n; i++) read(a[i]);
	for (rei i = 1; i <= n; i++)
	{
		while (top && a[st[top]] > a[i]) top--;
		if (!top) ls[i] = st[top + 1];
		else ls[i] = rs[st[top]], rs[st[top]] = i;
		st[++top] = i;
	}
	for (rei i = 1; i <= n; i++) ansl ^= (1ll * i * (ls[i] + 1)), ansr ^= (1ll * i * (rs[i] + 1));
	printf("%lld %lld", ansl, ansr);
	return 0;
}

例题1

P1377 [TJOI2011]树的序

此题与模板不同在于，位置号码为 $w$ 值，元素内数字为 $k$ 值。

则需对原数组排序，再按排序后顺序建树。

求 $k$ 值字典序最小，根据二叉查找树性质，答案为先序遍历结果。

顺便得出结论：谁有二叉查找树性质，就要按其顺序建树。

#include <bits/stdc++.h>
#define rei register int
#define N 100010
using namespace std;

template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	x *= f;
}

int n, st[N], top, x, ls[N], rs[N];
struct Node {int k, w;} a[N];

inline void Dfs(int u)
{
	printf("%d ", u);
	if (ls[u]) Dfs(ls[u]);
	if (rs[u]) Dfs(rs[u]);
}

inline bool cmp(const Node &a, const Node &b) {return a.k < b.k;}

int main()
{
	read(n);
	for (rei i = 1; i <= n; i++) read(a[i].k), a[i].w = i;
	sort(a + 1, a + 1 + n, cmp);
	for (rei i = 1; i <= n; i++)
	{
		while (top && a[st[top]].w > a[i].w) top--;
		if (!top) ls[i] = st[top + 1];
		else ls[i] = rs[st[top]], rs[st[top]] = i;
		st[++top] = i;
	}
	Dfs(st[1]);
	return 0;
}