首页 > 其他分享 >笛卡尔树

笛卡尔树

时间：2024-06-11 22:45:18浏览次数：14  
标签：笛卡尔 int top stk rg inline

笛卡尔树

引入

笛卡尔树是一种二叉树，每一个节点由一个键值二元组\((k,w)\)构成。要求k满足二叉搜索树的性质，而w满足堆的性质。 一个有趣的事实是，如果笛卡尔树的\(k,w\)键值确定，且k互不相同，w互不相同，那么这个笛卡尔树的结构是唯一的。

上面这棵笛卡尔树相当于把数组元素当作键值w，而把数组下标当作键值k。显然可以发现，这棵树的键值k满足二叉搜索树的性质，而键值w满足小根堆的性质。
其实图中的笛卡尔树是一种特殊的情况，因为二元组的键值k恰好对应数组下标，这种特殊的笛卡尔树有一个性质，就是一棵子树内的下标是一个连续的区间（这样才能满足二叉搜索树的性质）。更一般的情况则是任意二元组构建的笛卡尔树。

构建

栈构建

过程

我们考虑将元素按照键值k排序。然后一个一个插入到当前的笛卡尔树中。那么每次我们插入的元素必然在这个树的右链（从根节点一直往右子树走形成的链）的末端。于是我们执行这样一个过程，从下往上比较右链节点与当前节点u的w，如果找到了一个右链上的节点x满足\(x_w<u_w\)，就把u接到x的右儿子上，而x原本的右子树就变成u的左子树。

显然每个数最多进出右链一次（或者说每个点在右链中存在的是一段连续的时间）。这个过程我们可以用栈维护，栈中维护当前笛卡尔树的右链上的节点。一个点不在右链上了就把它弹掉。这样每个点最多进出一次，复杂度\(O(n)\)。

笛卡尔树与treap

treap其实是笛卡尔树的一种，只不过w的值完全随机。treap也有线性的构建算法，如果提前将元素排好序，显然可以使用上述单调栈算法完成构建过程，只不过很少会这么用。

例题1：【模板】笛卡尔树

板子。

#include<bits/stdc++.h>
#define rg register
#define qwq 0
#define ll long long
using namespace std;
const int N = 1e7 + 3;
int n, a[N], d[N];
int stk[N], top;
int ls[N], rs[N];
ll lans, rans;
inline void build() {
	for (rg int i = 1; i <= n; i++) {
		while (top && a[stk[top]] > a[i]) ls[i] = stk[top--];
		if (top) rs[stk[top]] = i;
		stk[++top] = i;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for (rg int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build();
	for (rg int i = 1; i <= n; i++) {
		lans ^= 1ll * i * (ls[i] + 1);
		rans ^= 1ll * i * (rs[i] + 1);
	}
	cout << lans << " " << rans << "\n";
	return qwq;
}

例题2：HDU1506 最大子矩形

我们把下标作为键值k，\(h_i\)作为键值w满足小根堆性质，构建一颗\((i,h_i)\)的笛卡尔树。
这样我们枚举每个节点u，把\(u_w\)（即高度值h）作为最大子矩阵的高度。由于我们建立的笛卡尔树满足小根堆性质，因此u的子树内的节点的高度都大于等于u。而我们又知道u子树内的下标是一段连续区间。于是我们只需要知道子树的大小，然后就可以算这个区间的最大子矩阵的面积了。用每一个点计算出来的值更新答案即可。显然这个可以一次dfs完成，因此复杂度是\(O(n)\)的。

#include<bits/stdc++.h>
#define rg register
#define qwq 0
#define ll long long 
using namespace std;
const int N = 1e5 + 3;
int n;
int top, stk[N];
int v[N], ls[N], rs[N];
ll ans;
inline void build() {
	stk[++top] = 0;  //为了保证笛卡尔树的根节点是0的右儿子，便于dfs 
	for (rg int i = 1; i <= n; i++) {
		while (top && v[stk[top]] > v[i]) ls[i] = stk[top--];
		if (top) rs[stk[top]] = i;
		stk[++top] = i;
	}
}
inline int dfs(int x) {  //一次dfs更新答案就可以了
	if (!x) return qwq;
	rg int siz = dfs(ls[x]);
	siz += dfs(rs[x]);
	ans = max(ans, (ll)(siz + 1) * v[x]);
	return siz + 1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	while (cin >> n && n) {
		memset(ls, 0, sizeof(ls));
		memset(rs, 0, sizeof(rs));
		memset(stk, 0, sizeof(stk));
		top = 0;
		for (rg int i = 1; i <= n; i++) {
			cin >> v[i];
		}
		build();
		ans = 0;
		dfs(rs[0]);
		cout << ans << "\n";
	}
	return qwq;
}

例题3：[TJOI2011] 树的序

题目中的输入要满足二叉搜索树的性质，所以对应键值k。于是令i值为键值w，建立笛卡尔树。
因为要求字典序最小，而二叉搜索树又满足左儿子<父节点<右儿子，所以先序遍历输出即可。

#include<bits/stdc++.h>
#define rg register
#define qwq 0
using namespace std;
const int N = 1e5 + 3;
int n;
int a[N], stk[N], top;
int ls[N], rs[N];
inline void build() {
	stk[++top] = 0;
	for (rg int i = 1; i <= n; i++) {
		while (top && a[stk[top]] > a[i]) ls[i] = stk[top--];
		if (top) rs[stk[top]] = i;
		stk[++top] = i;
	}
}
inline void dfs(int rt) {
	if(!rt) return ;
	cout << rt << " ";
	dfs(ls[rt]);
	dfs(rs[rt]);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for (rg int i = 1; i <= n; i++) {
		rg int v;
		cin >> v;
		a[v] = i;
	}
	build();
	dfs(rs[0]);
	return qwq;
}

例题4：[hdu6305]RMQ Similar Sequence

如果A和B是RMQ Similar，则A和B的笛卡尔树同构。因为B中的每个数是\(0\sim1\)之间的实数，因此出现相同数字的概率近似为0，可以假设B中每个数都不同。设A的笛卡尔树每个子树的大小为\(siz[i]\)，则任一B排列与A同构的概率是\(\displaystyle\prod_1^n\frac{1}{siz[i]}\)。因为B中每个数满足均匀分布，因此期望值为\(\frac1 2\)，和的期望值为\(\frac n 2\)，因此满足于A同构的B中所有数之和的期望为\(\displaystyle\frac{n}{2\prod_1^n siz[i]}\)。
注意：
1.最后答案为分数形式，又要取模，因此要求逆元。
2.因为要求的是区间的最大值，因此要满足大根堆性质，即要求a[stk[top]] < a[i]。

#include<bits/stdc++.h>
#define rg register
#define qwq 0
#define int long long
using namespace std;
const int N = 1e6 + 3, mod = 1e9 + 7;
int T, n;
int a[N], stk[N], top;
int ls[N], rs[N];
inline void init() {
	top = 0;
	for (rg int i = 1; i <= n; i++) ls[i] = rs[i] = 0;
}
inline void build() {
	for (rg int i = 1; i <= n; i++) {
		while (top && a[stk[top]] < a[i]) ls[i] = stk[top--];
		if (top) rs[stk[top]] = i;
		stk[++top] = i;
	}
}
int siz[N];
inline int dfs(int rt) {  //求子树大小 
	if (!rt) return qwq;
	rg int res = dfs(ls[rt]);
	res += dfs(rs[rt]);
	res++;
	siz[rt] = res;
	return res;
}
inline int qpow(int a, int b) {
	rg int res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
inline int inv(int a) {
	return qpow(a, mod - 2);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> T;
	while (T--) {
		init();
		cin >> n;
		for (rg int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		build();
		dfs(stk[1]);
		rg int ans = 2;
		for (rg int i = 1; i <= n; i++) {
			ans = ans * siz[i] % mod;
		}
		cout << n * inv(ans) % mod << "\n";
	}
	return qwq;
}

例题5：[COCI2008-2009#4] PERIODNI

我们每次尽可能地删去整张表格的最低行，直到当前最低行已经不连通。将删去的行组成一个矩形，再将分开的至多两个连通块递归处理，就可以将原图分成若干个矩形。
样例3分成矩形后的图如下：

我们发现，这样构成的若干个矩形正好对应笛卡尔树上的所有节点，每次递归处理的两个小联通块正好是当前节点的两个儿子。根据定义，我们可以知道，对于节点x代表的矩形，它的长度为\(siz_x\)，高度为\(h_x-h_{son_x}\)。
这样，我们建出笛卡尔树，就可以把这一问题转化成书上背包问题。
定义\(f_{i,j}\)表示在子节点i子树所代表的区域内选择了j个格子的方案数，两个儿子的答案显然可以用树形背包合并，难点就只剩下如何计算与合并当前节点的方案了。
枚举当前节点所代表的矩形选了j个格子，子树内其余部分选了k个格子，我们可以将当前矩形的方案数表示成\(C_{siz_x-k}^{j}\times C_{h_x-h_{son_x}}^{j} \times j!\)，也就是选择行、列的方案数乘上j的全排列。
通过树上背包的siz优化，我们保证两个节点总是在它的LCA处合并。

#include<bits/stdc++.h>
#define rg register
#define qwq 0
#define int long long
using namespace std;
const int N = 503, M = 1e6 + 3, mod = 1e9 + 7;
int n, m;
int h[N], stk[N], top;
int ls[N], rs[N];
int f[N][N], siz[N];
int jie[M];
inline int qpow(int a, int b) {
	rg int res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
inline void init() {
	jie[0] = 1;
	for (rg int i = 1; i < M; i++) {
		jie[i] = jie[i - 1] * i % mod;
	}
}
inline int inv(int a) {
	return qpow(a, mod - 2);
}
inline int C(int a, int b) {
	return jie[a] * inv(jie[b]) % mod * inv(jie[a - b]) % mod;
}
inline void build() {
	for (rg int i = 1; i <= n; i++) {
		while (top && h[stk[top]] > h[i]) ls[i] = stk[top--];
		if (top) rs[stk[top]] = i;
		stk[++top] = i;
	}
}
inline void dfs(int u, int fath) {
	if (!u) return ;
	f[u][0] = 1;
	siz[u] = 1;
	rg int k = h[u] - h[fath];  //矩形的宽
	dfs(ls[u], u);
	siz[u] += siz[ls[u]];
	for (rg int i = min(siz[u], m); i; i--) {  //当前子树选的格子数 
		for (rg int j = 1; j <= min(siz[ls[u]], i); j++) {  //儿子的子树选的格子数 
			f[u][i] = (f[u][i] + f[ls[u]][j] * f[u][i - j]) % mod;
		}
	}
	dfs(rs[u], u);
	siz[u] += siz[rs[u]];
	for (rg int i = min(siz[u], m); i; i--) {
		for (rg int j = 1; j <= min(siz[rs[u]], i); j++) {
			f[u][i] = (f[u][i] + f[rs[u]][j] * f[u][i - j]) % mod;
		}
	}
	for (rg int i = min(siz[u], m); i; i--) {  //当前子树选的格子数 
		for (rg int j = 1; j <= min(k, i); j++) {  //当前节点所代表的矩形选了j个格子，即j行
			f[u][i] = (f[u][i] + f[u][i - j] * C(siz[u] - (i - j), j) % mod * C(k, j) % mod * jie[j] % mod) % mod;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	init();
	for (rg int i = 1; i <= n; i++) {
		cin >> h[i];
	}
	build();
	dfs(stk[1], 0);
	cout << f[stk[1]][m] << "\n";
	return qwq;
}

例题6：[hdu4125]Moles

建笛卡尔树，dfs找出遍历顺序（即欧拉序），然后kmp匹配即可。
编号符合二叉搜索树性质。
根据题意，鼹鼠的编号满足二叉搜索树性质，于是编号为数组下标。又要求先经过编号小的节点，可知要统计欧拉序（因为满足二叉搜索树的性质，所以能保证编号小的节点在左子树上）。
统计出欧拉序后，将其作为文本串，与模式串进行匹配，使用KMP即可。

#include<bits/stdc++.h>
#define rg register
#define qwq 0
using namespace std;
const int N = 6e5 + 3;
int T, n;
int a[N], ls[N], rs[N];
int top, stk[N];
string s, t;
inline void init() {
	top = 0;
	for (rg int i = 1; i <= n; i++) {
		ls[i] = rs[i] = 0;
	}
	s = "";
}
inline void build() {
	for (rg int i = 1; i <= n; i++) {
		while (top && a[stk[top]] > a[i]) ls[i] = stk[top--];
		if (top) rs[stk[top]] = i;
		stk[++top] = i;
	}
}
inline void add(int u) {
	if (u & 1) s += '1';
	else s += '0';
}
inline void dfs(int u) {
	add(u);
	if (ls[u]) {
		dfs(ls[u]);
		add(u);
	}
	if (rs[u]) {
		dfs(rs[u]);
		add(u);
	}
}
int nxt[N];
inline void get_next() {  //在模式串上找失配指针
	rg int j = 0, k = -1;
	nxt[0] = -1;
	rg int lent = t.length();
	while (j < lent) {
		if (k == -1 || t[j] == t[k]) {  //如果当前位匹配，j、k都向右移继续匹配 
			j++;
			k++;
			if (t[j] == t[k]) nxt[j] = nxt[k];  //因为如果这一位匹配不上，那么这一位的失配指针也匹配不上，直接跳到最早出现的位置 
			else nxt[j] = k;
		} else k = nxt[k];
	}
}
inline int KMP() {
	rg int i = 0, j = 0, cnt = 0;
	rg int lens = s.length(), lent = t.length();
	get_next();
	while (i < lens) {
		if (j == -1 || s[i] == t[j]) {  //这一位匹配成功，向右移继续匹配 
			i++;
			j++;
		} else j = nxt[j];
		if (j == lent) {  //如果当前匹配成功的长度与模式串长度相等，cnt++，跳指针匹配下一次 
			cnt++;
			j = nxt[j];
		}
	}
	return cnt;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> T;
	for (rg int tt = 1; tt <= T; tt++) {
		init();
		cin >> n;
		for (rg int i = 1; i <= n; i++) {
			rg int d;
			cin >> d;
			a[d] = i;
		}
		cin >> t;
		build();
		dfs(stk[1]);
		cout << "Case #" << tt << ": " << KMP() << "\n";
	}
	return qwq;
}

例题7：[hdu6854]Kcats

a[]就是右链的长度。
区间dp。

【颓题解】
\(a_i\)为最后的笛卡尔树上，第i个节点的所有祖先中k值比自己小的节点的数量。接着考虑区间dp，令\(f_{l,r,d}\)表示区间\([l,r]\)所对应的笛卡尔树的根节点的祖先中有d个k值比自己小。那么它的左儿子节点，即区间\([l,rt)\)的根节点的有贡献的祖先节点一定和它的祖先节点是一样的。但是它的右儿子节点，即区间\((rt,r]\)的根节点不仅有它有的祖先节点，还包含它本身。因为笛卡尔树满足小根堆，所以它的左子树一定比它大且按顺序排列，因此数字的组合可能为\(C_{r-l}^{k-l}\)。转移方程为：

\[f_{l,r,d}=\displaystyle\sum_{k-i}^{j} \begin{cases} \sum_{d=a_k}f_{l,k-1,d}\times f_{k+1,r,d+1}\times C_{r-l}^{k-l}(a_k\ne -1) \\ \sum_{d=1}^{n}f_{l,k-1,d}\times f_{k+1,r,d+1}\times C_{r-1}^{k-l}(a_k=-1) \end{cases} \]

#include<bits/stdc++.h>
#define rg register
#define qwq 0
#define int long long
using namespace std;
const int N = 103, mod = 1e9 + 7;
int T, n, ll, rr;
int a[N];
int f[N], g[N], dp[N][N][N];
inline int qpow(int a, int b) {
	rg int res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
inline void get() {
	f[0] = 1;
	for (rg int i = 1; i < N; i++) {
		f[i] = f[i - 1] * i % mod;
	}
	g[N - 1] = qpow(f[N - 1], mod - 2);
	for (rg int i = N - 2; i >= 0; i--) {
		g[i] = g[i + 1] * (i + 1) % mod;
	}
}
inline int C(int a, int b) {
	return f[a] * g[b] % mod * g[a - b] % mod;
}
inline void init() {
	for (rg int i = 1; i <= n; i++) {
		for (rg int j = 1; j <= n; j++) {
			for (rg  int k = 1; k <= n; k++) dp[i][j][k] = 0;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	get();
	cin >> T;
	while (T--) {
		cin >> n;
		init();
		for (rg int i = 1; i <= n; i++) cin >> a[i];
		for (rg int len = 1; len <= n; len++) {
			for (rg int l = n - len + 1; l >= 1; l--) {
				rg int r = l + len - 1;
				for (rg int k = l; k <= r; k++) {
					if (a[k] == -1) {
						ll = 1;
						rr = n;
					} else {
						ll = rr = a[k];
					}
					for (rg int d = ll; d <= rr; d++) {
						dp[l][r][d] = (dp[l][r][d] + (l < k ? dp[l][k - 1][d] : 1) * (k < r ? dp[k + 1][r][d + 1] : 1) % mod * C(r - l, k - l) % mod) % mod;
					}
				}
			}
		}
		cout << dp[1][n][1] << "\n";
	}
	return qwq;
}

完结撒花~

标签：笛卡尔,int,top,stk,rg,inline
From： https://www.cnblogs.com/Baiyj/p/18242908

相关文章

  • 赛克oj The diameter of a rectangle（笛卡尔树）
    赛氪OJ-专注于算法竞赛的在线评测系统(saikr.com)这题是hduoj1506的加强版，区别在于宽度不是固定为1了，思路差不多，也是使用笛卡尔树。参考hduoj1506（笛卡尔树）-Venux-博客园(cnblogs.com)1#defineIOstd::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)2#definebu......
  • hduoj 1506（笛卡尔树）
    Problem-1506(hdu.edu.cn)题意坐标轴给定一些矩形，紧密排在一起，每个矩形宽度固定为1，问形成的图案中最大可以组成的矩形面积。思路常规思路是可以用单调栈分别找两边的合法边界，这里使用笛卡尔树。笛卡尔树实现了堆的性质，并且对原数组建立的笛卡尔树进行中序遍历为原数组的顺......
  • [NOI2009] 二叉查找树 & 笛卡尔树学习笔记
    这个题：二叉搜索树原理认识+区间dp；只要熟练相关算法就一定可以做出来。但我不行。。。我们学习一下笛卡尔树：什么垃圾东西，不学了。发现这个题是l蓝书上一道题jqb。二叉查找树又有一个性质：二叉查找树的中序遍历是其代表的序列从小到大排序的结果。而无论Treap如何旋转，其都......
  • 笛卡尔树学习笔记
    笛卡尔树引入是一种二叉树，每个节点由一个二元组\((k,w)\)形成。\(k\)满足二叉搜索树的性质，\(w\)满足堆的性质。上面这棵笛卡尔树相当于把数组元素值当作键值\(w\)，而把数组下标当作键值\(k\)。显然可以发现，这棵树的键值\(k\)满足二叉搜索树的性质，而键值\(w\)满足小根......
  • 生成带重复的笛卡尔乘积过程 Cartesian Product with Repetition
    目录WhatisCartesianProductwithRepetitionCodeDemoWhatisCartesianProductwithRepetition比如说有两个集合：\(\{1,2,3\}\)\(\{A,B,C\}\)想把他们组合成所有可能组合，比如，1AAA1AAB1AAC...这种组合可以称为"有重复的笛卡尔积"或"带重复的笛卡尔乘积"(Carte......
  • 笛卡尔树
    笛卡尔树实际上就是对于多个二元组\((k_i,w_i)\)的一棵树，使其所有\(k\)值满足二叉搜索树的性质，且所有\(w\)值都满足小根堆的性质。在构建时，对于右链上的元素，自底向上一定是\(w\)值由小到大的，且一定\(k\)值从小到大。所以我们按\(k\)值从小到大排序，比并按顺序插入右......
  • vue 商品sku添加，笛卡尔算法，商品添加。动态生成table，table添加值后 再生成的table 不
     <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>快速入门</title><!--引入组件库--><linkrel="stylesheet"href="https://un......
  • vue 商品sku，笛卡尔算法，商品添加。动态生成table，table添加值后 再生成的table 不改变t
     <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>快速入门</title><!--引入组件库--><linkrel="stylesheet"href="https://un......
  • 笛卡尔树
    1定义笛卡尔树是一种二叉树，每一个节点由二元组\((k,w)\)组成。要求\(k\)满足二叉搜索树的性质，\(w\)满足堆的性质。当\(k,w\)都确定，且\(k,w\)互不相同时，笛卡尔树的结构是唯一的，如图：看到这个定义，会发现与Treap十分相似。实际上，Treap就是一种特殊的笛卡尔树。通......
  • P7219 [JOISC2020] 星座 3【笛卡尔树+整体dp】
    P7219[JOISC2020]星座3笛卡尔树+整体dp（线段树合并维护dp）考虑转化题意，不存在矩形为星座，即对于每个极大矩形中都只有一颗星星。而观察题目的方格，对于两个位置是否能够成为一个矩形，只和两个位置的区间最大值（小白船的位置）有关①。图中的红蓝矩形即为两个极大矩形。将删除星......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99