1 定义
给定数组
- 下标有序:左子树中所有下标小于
,右子树中所有下标大于 。 - 权值成堆:父节点的权值不大于子节点的权值。
因此,中序遍历得到下标
若权值相等,仅凭这两条性质不能确定唯一结构。本文统一按
例如数组 下标:权值。
根是节点
2 递归建树
对于区间
这样的划分保持了下标顺序,根的权值也不大于两棵子树中的任意权值。反过来,任何满足约定的笛卡尔树,其根都只能是这个
直接扫描区间寻找最小值,最坏需要
为了避免重复扫描,可以从左到右插入节点,用 单调栈 维护正在变化的部分。
3 单调栈
已经插入
用栈保存这条路径:栈底是根,沿右孩子依次走到栈顶。路径上权值不下降;权值相等时,下标递增。
3.1 插入节点
从栈顶开始,弹出所有权值严格大于 last。
- 若栈仍非空,把栈顶的右孩子改为
。 - 把
的左孩子设为 last。 - 把
入栈,得到新的最右侧路径。
没有节点弹出时,last=0,新节点没有左孩子。若整个栈都被弹空,新节点成为根,旧树整体成为它的左子树。
3.2 连续弹栈
对于数组
新权值
弹栈后剩下节点 rs[2]=5、ls[5]=3。节点
弹栈只是移出维护路径,节点仍然保留在树中。 也不能把每个弹出的节点分别设为新节点的左孩子;应把最后弹出节点所代表的整棵子树接过去。
| 插入节点 | 弹出的下标 | 插入后的栈(下标) |
|---|---|---|
1:3 |
无 | [1] |
2:1 |
1 |
[2] |
3:4 |
无 | [2,3] |
4:5 |
无 | [2,3,4] |
5:2 |
4,3 |
[2,5] |
3.3 正确性
假设插入前的树已经满足定义。被弹出的节点构成最右路径的一段,其最后弹出节点 last 是这部分子树的根。
新节点
last 的权值大于
新树的最右侧路径恰好是保留的栈前缀再加上
4 线性构造
主例:luogu P5854: 笛卡尔树。题目给定一个
用普通数组 ls、rs 记录左右孩子,0 表示不存在。核心构造集中在 build 中,返回根的下标。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10000000 + 5; // P5854 的 n 最大为 10^7
int a[maxn], ls[maxn], rs[maxn], st[maxn];
int build(int n) {
int top = 0;
for (int i = 1; i <= n; ++i) {
int last = 0;
ls[i] = rs[i] = 0;
// st 保存当前树从根到最右节点的路径。
// 只弹出权值更大的节点:相等时,先出现的节点优先。
while (top && a[st[top]] > a[i]) last = st[top--];
if (top) rs[st[top]] = i; // i 接到未弹出节点的右侧
ls[i] = last; // 最后弹出的节点,其整棵子树移到 i 左侧
st[++top] = i;
}
return top ? st[1] : 0; // 栈底始终是根;空树返回 0
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(n); // 构造并填充左右孩子数组
ll answer_l = 0, answer_r = 0;
for (int i = 1; i <= n; ++i) {
// 先转为 long long 再乘,避免 int 乘法溢出。
answer_l ^= 1LL * i * (ls[i] + 1);
answer_r ^= 1LL * i * (rs[i] + 1);
}
cout << answer_l << ' ' << answer_r << '\n';
return 0;
}
虽然有两层循环,但每个节点只入栈一次、出栈至多一次,全部弹栈次数不超过
实现时注意:
- 弹栈条件为
>,使相等值中较小下标优先。若改成>=,则变为较大下标优先,区间最小值位置的约定也要随之改变。 - 根在栈底
st[1],栈顶只是当前最右侧节点。 - P5854 的
可达 ,四个 int数组约占MB;处理较小数据时应按实际范围调整 maxn。校验值的乘法必须先转成long long。
5 区间性质
5.1 子树对应连续区间
一棵子树的中序遍历会连续完成,不会与子树外的节点交错。由于整棵树的中序遍历是
再由堆性质,子树根
这是中序下标区间,不要与一般树中通过 DFS 编号得到的子树区间混淆。
5.2 区间最值与 LCA
任取
若
同时,
例如
这把静态区间最小值查询(RMQ)转化为 LCA 查询。线性建树之后,仍需选择相应的 LCA 算法;使用 爬树法求 LCA(倍增) 时,预处理为
6 最大矩形
题目:roj 3032: 「Largest Rectangle in a Histogram」 直方图中最大的矩形。
每根柱子宽度为
对高度数组建立笛卡尔树。每个节点
对示例数组,节点
6.1 不漏最优解
任取区间
右侧也是一个合法矩形的面积。也就是说,任何区间都能扩展到某棵子树的区间,保持最低高度不变,面积不会减小。所以答案恰好是:
这个证明也适用于重复高度。不要因此认定每个节点的子树都是该高度能延伸到的最大范围:例如
6.2 代码实现
构造后,用迭代遍历记录“父亲先于孩子”的访问顺序,再倒序计算子树大小。这样即使树退化成链,也不依赖深递归。
约定 long long。
完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
int a[maxn], ls[maxn], rs[maxn], st[maxn];
int order[maxn], siz[maxn];
int build(int n) {
int top = 0;
for (int i = 1; i <= n; ++i) {
int last = 0;
ls[i] = rs[i] = 0; // 多组输入时清除上一棵树的孩子
while (top && a[st[top]] > a[i]) last = st[top--];
if (top) rs[st[top]] = i;
ls[i] = last;
st[++top] = i;
}
return top ? st[1] : 0;
}
ll largest_rectangle(int root) {
int top = 0, count = 0;
if (root) st[++top] = root;
while (top) {
int u = st[top--];
order[++count] = u; // 先记录父亲,再访问孩子
if (ls[u]) st[++top] = ls[u];
if (rs[u]) st[++top] = rs[u];
}
ll answer = 0;
// 倒序处理,保证两个孩子的子树大小已经算完。
for (int i = count; i >= 1; --i) {
int u = order[i];
siz[u] = siz[ls[u]] + siz[rs[u]] + 1; // siz[0] 始终为 0
answer = max(answer, 1LL * a[u] * siz[u]);
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while (cin >> n && n) {
for (int i = 1; i <= n; ++i) cin >> a[i];
cout << largest_rectangle(build(n)) << '\n';
}
return 0;
}
直接使用单调栈求边界的实现见 pcs2:直方图中最大的矩形。笛卡尔树把这类按区间最小值划分的问题,显式组织成了一棵树。
7 相关题解
暂无相关题解