笛卡尔树(Cartesian Tree)

定义

给定一个序列 $a$ ,笛卡尔树的中序遍历为该序列.
笛卡尔树满足堆的性质.

性质 & 应用

查找 $t o p k$ .
令 $x$ , $y$ 为节点序号(按照原序列 $a$ 排序), $L C A (x, y) == R M Q (x, y)$ .

建树

考虑元素插入。

元素按照序列顺序插入笛卡尔树时，首先需要满足树的中序遍历仍为原序列，即让插入的数必须在树的右链上。

与此同时需要满足堆的性质，考虑用单调栈进行维护。

已知当前待插入节点的权值为 $w$ , 从根节点开始查找右链上的值.

如果找到一个值 $u$ 使得 $u < w$ 且 $u_{r s} > w$ ,则将 $u_{r s}$ 接到 $w$ 的左子树上,将 $w$ 接到 $u$ 的右子树上.

否则直接将 $w$ 接到树的右链的最末尾.

图中红色框框部分就是我们始终维护的右链.(来源:OI-wiki)

代码

伪代码:

新建一个大小为 n 的空栈。用 top 来标操作前的栈顶，k 来标记当前栈顶。
For i := 1 to n
    k := top
    While 栈非空 且 栈顶元素 > 当前元素 
        k--
    if 栈非空
        栈顶元素.右儿子 := 当前元素
    if k < top
        当前元素.左儿子 := 栈顶元素
    当前元素入栈
    top := k

cpp:

cpp

for (int i = 1; i <= n; i++) {
  int k = top;
  while (k > 0 && h[stk[k]] > h[i]) k--;
  if (k) rs[stk[k]] = i;  // rs代表笛卡尔树每个节点的右儿子
  if (k < top) ls[i] = stk[k + 1];  // ls代表笛卡尔树每个节点的左儿子
  stk[++k] = i;
  top = k;
}

例题

acwing 4279 笛卡尔树

cpp

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <bitset>

using std::cin;using std::cout;using std::cerr;using std::endl;

#define rep(i,a,b) for(int i = a;i <= b;++i)
#define per(i,a,b) for(int i = a;i >= b;--i)

typedef long long ll;
typedef unsigned long long ull;

const int mmax = 50;
int a[mmax],ls[mmax],rs[mmax],s[mmax];
int root,top,n;

std::queue<int> q[mmax];

void dfs(int x,int n){
	q[n].push(a[x]);
	if(ls[x]) dfs(ls[x],n + 1);
	if(rs[x]) dfs(rs[x],n + 1);
}

int main(){

	std::ios::sync_with_stdio(0);
	cin.tie(0);

	cin>>n;
	rep(i,1,n){
		cin>>a[i];
		int k = top;
		while(k && a[s[k]] > a[i]) k--;
		
		if(k) rs[s[k]] = i;
		else root = i;
		if(k < top) ls[i] = s[k + 1];
		
		s[++k] = i;
		top = k;
	}

	dfs(root,1);
	rep(i,1,n){
		while(!q[i].empty()){
			cout<<q[i].front()<<' ';
			q[i].pop();
		}
	}

	return 0;
}

Luogu p5854 【模板】笛卡尔树

注意，此题卡读入。

cpp

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <bitset>

using std::cin;using std::cout;using std::cerr;using std::endl;

#define rep(i,a,b) for(int i = a;i <= b;++i)
#define per(i,a,b) for(int i = a;i >= b;--i)

typedef long long ll;
typedef unsigned long long ull;

const int mmax = 1e7 + 10;
ll n,lans,rans,top;
ll a[mmax],ls[mmax],rs[mmax],s[mmax];

ll read(){
	ll x = 0,f = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = x * 10 + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}

int main(){

	std::ios::sync_with_stdio(0);
	cin.tie(0);


	n = read();

	rep(i,1,n){
		a[i] = read();
		int t = top;
		while(t && a[s[t]] > a[i]) t--;
		if(t) rs[s[t]] = i;
		if(t < top) ls[i] = s[t + 1];
		s[++t] = i;
		top = t;
	}
	rep(i,1,n){
		lans ^= (long long) i * (ls[i] + 1);
		rans ^= (long long) i * (rs[i] + 1);
	}
	cout<<lans<<' '<<rans;

	return 0;
}

[TJOI2011] 树的序

题目描述

二叉查找树的形态和键值的插入顺序密切相关。准确的讲：

空树中加入一个键值k，则变为只有一个结点的二叉查找树，此结点的键值即为k；
在非空树中插入一个键值k，若k小于其根的键值，则在其左子树中插入k，否则在其右子树中插入k。

我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个，其中，字典序关系是指对两个长度同为n的生成序列，先比较第一个插入键值，再比较第二个，依此类推。

为了简单起见，生成序列 $y_{1} . . . y_{n}$ 为一个 $1$ 到 $n$ 的排列。

思路

考虑将每次插入的数看作有序对 $< x_{i}, y_{i} >$ ,其中 $x$ 是插入顺序, $y$ 是插入键值.

二叉查找树的中序遍历 $y$ 有序.
二叉查找树的儿子一定比父亲晚插入树,即 $x$ 满足堆的性质.
$y_{1} . . . y_{n}$ 为一个 $1$ 到 $n$ 的排列。

其中 $3$ 可以改为两两不相同的正数,再用离散化处理即可.

我们不妨取有序对的逆 $< y_{i}, x_{i} >$ ,再回来看我们的树,由 $1$ 和 $2$ 可以发现它等同于把 $y$ 作为插入顺序,把 $x$ 作为键值的笛卡尔树!

那么生成序列中字典序最小的就是对笛卡尔树先序遍历的 $y$ 值.

cpp

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <bitset>

using std::cin;using std::cout;using std::cerr;using std::endl;

#define rep(i,a,b) for(int i = a;i <= b;++i)
#define per(i,a,b) for(int i = a;i >= b;--i)

typedef long long ll;
typedef unsigned long long ull;

const int mmax = 1e5 + 10;
int a[mmax],ls[mmax],rs[mmax],s[mmax];
int top,root,n,y;

void dfs(int x){
	cout<<x<<' ';
	if(ls[x]) dfs(ls[x]);
	if(rs[x]) dfs(rs[x]);
}

int main(){

	std::ios::sync_with_stdio(0);
	cin.tie(0);

	cin>>n;
	rep(i,1,n){
		cin>>y;
		a[y] = i;
	}
	
	rep(i,1,n){
		int k = top;
		while(k && a[s[k]] > a[i]) k--;
		if(k) rs[s[k]] = i;
		else root = i;
		if(k < top) ls[i] = s[k + 1];
		s[++k] = i;
		top = k;
	}
	dfs(root);

	return 0;
}

笛卡尔树(Cartesian Tree) ​

定义 ​

性质 & 应用 ​

建树 ​

代码 ​

伪代码: ​

cpp: ​

例题 ​

acwing 4279 笛卡尔树 ​

Luogu p5854 【模板】笛卡尔树 ​

[TJOI2011] 树的序 ​

题目描述 ​

思路 ​

参考 ​