今天打卡信奥刷题第 2943 题正好是 P5854【模板】笛卡尔树。这道题在我眼里是典型的“一道题贯通三块知识”的模板它把线性结构、二叉树结构和单调栈算法串在同一条主线上很多训练列表把它放在树形结构专题的起点不是没有道理。如果你刚学完单调栈或者正准备往 RMQ、Treap 这些方向深入这题非常值得停下来认真拆一遍。题面本身不复杂给一个 1 到 n 的排列要求构造出对应的笛卡尔树并按顺序输出每个节点的左儿子和右儿子。但真正有挑战的是数据规模n 可以到千万量级这对构建算法的复杂度、输入输出速度和内存布局都提出了硬性要求。换句话说这题不是让你“会写笛卡尔树”就够而是要你写出能在极限数据下稳定运行的版本。下面我把拆题思考、构造原理、C 实现和调试经验一起整理出来。1. 先拆题模板题到底要你交出什么1.1 三句话看懂输入输出和隐藏条件P5854 的输入格式很简单第一行一个正整数 n第二行 n 个整数是 1 到 n 的一个排列。输出是两行第一行 n 个整数第 i 个数表示第 i 个节点的左儿子编号第二行是右儿子编号没有儿子就输出 0。这里有一个容易被新手忽略的点题目里说的“第 i 个节点”对应的就是输入序列中下标为 i 的位置而不是数值 a[i]。节点编号和输入数组下标完全绑定节点的权值才是 a[i]。换句话说你构建的笛卡尔树每个节点携带一个“下标号”和一个“数值权”下标号体现的是中序遍历顺序数值权体现的是堆序。搞清楚这个区分后面理解构造算法会顺很多。隐藏条件才是这题的真正门槛n 可以到 10^7 这个量级。别小看这一条它直接淘汰了好几种看似正确的做法。比如每次都递归找区间最小值来建树平均情况下很快但遇到有序数据会退化到 O(n²)再比如用线段树辅助找区间最小值复杂度能压到 O(n log n)但千万级数据下常数太大时间同样危险。所以模板题真正想让你掌握的是基于单调栈的 O(n) 线性构造法。1.2 为什么朴素构造会翻车讲单调栈之前先看一眼最直观的递归法在区间 [l, r] 中找到最小值所在位置 k以 k 为根递归处理 [l, k-1] 和 [k1, r]。这个思路完全贴合笛卡尔树的定义但它的问题也很明显。如果输入恰好是一个升序序列比如 1,2,3,...,n那么每次找出的最小值都在区间最左边。第一次要扫描 n 个元素第二次扫描 n-1 个累计下来就是 O(n²) 次比较n 到 10^7 时这个数字大到完全无法接受。就算用线段树把“找最小值位置”优化到 O(log n)整体 O(n log n) 在千万级数据下依然偏慢而且线段树本身还要额外开几倍空间。相比之下单调栈做法每个元素最多入栈一次、出栈一次总操作次数是线性级别空间也只有若干个数组这才是模板该有的样子。2. 单调栈构造法一条右链撑起整棵树2.1 笛卡尔树的两条铁律笛卡尔树是同时满足两个条件的二叉树。第一条是中序遍历必须还原成原始序列你按中序遍历这棵树走出来的节点下标正好是 1,2,...,n。第二条是堆序如果用小根堆版本那么每个节点的权值 a[i] 都不大于它的左右孩子权值。根节点就是整个区间的最小值而每个子树也对应原数组的一个连续区间。这两条性质合在一起就注定了笛卡尔树在无重复元素的排列输入下是唯一的。你可以把下标想象成“排队位置”把权值想象成“优先级”笛卡尔树就是让排队顺序和优先级层次同时成立的一棵二叉树。这也是它能在很多场景里替代 RMQ、LCA 的底层原因——两把“锁”一锁结构几乎没有自由度。有了这两条铁律你就能解释构造过程中的每个动作。为什么新元素总是出现在右链上因为按 1 到 n 的顺序插入新节点在下标顺序上永远排在已插入节点的最后而中序遍历要保持原序列顺序所以新节点只能挂在前一棵树的右侧某个位置并且它一旦接上原来的右链中比它优先级低的部分要整体挪到它的左子树去。2.2 为什么只需要维护右链构建过程从左到右扫描数组任何时候已经处理完前 i 个元素。此时已经形成的笛卡尔树它的最右链就是从根节点开始一路沿着右孩子走到最右下端的路径。因为新节点在序列的最右边它插入时只会影响这条最右链上的节点关系左子树一旦成型就再也不会被改动。这件事是单调栈解法的核心洞察。所以我们不需要真的动态维护整棵树的平衡或形态只需要用一个栈来存放当前最右链。栈底是当前树的根栈顶是最右下端的节点栈内元素从底到顶对应最右链从上到下而且在小根堆性质下这些节点的权值从栈底到栈顶是严格递增的。每次来一个新节点先沿着栈顶方向找到第一个权值比它小的节点这个节点就是它在最右链上的“父亲候选”那些权值比它大的右链节点会被整体切下来变成新节点的左子树。2.3 弹出、接左、覆盖右三步完成一次插入具体操作可以拆成三步。假设当前扫描到下标 i权值为 x a[i]。第一步是弹栈。不断看栈顶元素只要栈非空且 a[st[top]] x就把栈顶弹出并用一个变量 last 记录最后被弹出的节点编号。循环结束时last 就是从原右链上被切下来的那段链的“根”也就是离新节点最近的那个被弹出节点。第二步是接右。如果弹完栈后栈仍然非空说明此时栈顶的权值比 x 小它就是新节点在右链上的父亲把它的右儿子指针指向 i。这里有个容易困惑的点这个节点的右儿子可能之前已经有值现在被新节点覆盖了。其实覆盖是正常的被覆盖掉的那个旧右儿子一定已经在弹栈过程中被记入 last 链最终会成为新节点的左后代。第三步是接左。把 last 作为 i 的左儿子。因为 last 以及它代表的整段链在序列位置上都位于 i 的左边权值又都比 x 大所以它们作为 i 的左子树完全符合两条铁律。最后把 i 入栈它成为新的最右链端点。我拿一组小数据走一遍。假设 n6a[4,1,3,2,5,6]i1x4栈空lc[1]0压栈栈为 [1]。i2x1a[1]41弹出 1last1栈空lc[2]1压栈栈为 [2]。此时 2 成为根1 是它的左孩子。i3x3a[2]13不弹栈顶是 2rc[2]3压栈栈为 [2,3]。i4x2a[3]32弹出 3last3此时 a[2]12停止栈顶是 2rc[2]4lc[4]3压栈栈为 [2,4]。这一步里 rc[2] 从 3 被覆盖成 4而 3 变成了 4 的左孩子正好对应上面说的覆盖规则。i5x5a[4]25rc[4]5压栈栈为 [2,4,5]。i6x6a[5]56rc[5]6压栈栈为 [2,4,5,6]。最终中序遍历是 1,2,3,4,5,6并且父节点的权值都不大于儿子完全正确。2.4 等值数据怎么处理P5854 给的是排列没有重复值所以无论用还是作为弹出条件都能过。但如果你的数据不是排列而是可能包含相等整数的普通数组这里就要认真想一下了。以构建小根堆笛卡尔树为例弹栈条件写成a[st[top]] a[i]遇到相等的新元素时不会弹出旧元素新元素会直接作为旧元素的右儿子接入。这样先出现的、下标较小的相等元素在树中会更“靠上”整体形态是稳定的。如果改成a[st[top]] a[i]相等的旧元素会被弹出最后变成新元素的左子树虽然中序遍历依然保持原序列但树的形态会略有不同。大多数模板题不关心这种差异可一旦你的后续代码依赖树的形态比如要从笛卡尔树推 LCA、做 RMQ就必须选定一种规则并固定下来。我的习惯是默认用保证相等元素“先到先得”调试时心智负担小。3. 手写C模板从数组规划到满速IO3.1 四个数组一个都不能少实现这道模板题你至少需要四个 int 数组。第一个是权值数组 a存每个节点的数值因为在构造过程中要反复比较 a[st[top]] 和 a[i]。第二个是左儿子数组 lc第三个是右儿子数组 rc分别在构造过程中和构造结束后使用。第四个是模拟单调栈的数组 st它存的是节点编号而不是权值。n 到 10^7 时四个数组每个大约需要 10^7 5 个 int按每个 int 4 字节计算合计约 160MB。这是一个必须提前规划的内存开销。我建议把数组全部开成全局静态数组不要写在 main 函数里也不要临时用 vector 动态分配。全局数组放在静态存储区不存在爆栈风险访问速度也比堆内存更稳定。数组大小可以统一开成const int MAXN 10000000 5。如果你的平台内存比较紧张比如只有 256MB 甚至 128MB开 4 个整型数组会非常极限这种情况下更要避免额外开辟任何多余的容器。好在这类模板题的内存限制通常会考虑到标准写法四数组方案是主流。3.2 核心构造代码可AC版本下面这份代码就是最标准的单调栈构造实现核心部分很短重点全在细节。#include cstdio const int MAXN 10000000 5; int a[MAXN], lc[MAXN], rc[MAXN], st[MAXN]; inline int read() { int x 0; char c getchar(); while (c 0 || c 9) c getchar(); while (c 0 c 9) { x (x 3) (x 1) (c ^ 48); c getchar(); } return x; } inline void writeInt(int x) { if (x 0) { putchar(0); return; } char buf[12]; int len 0; while (x) { buf[len] char(0 x % 10); x / 10; } while (len--) putchar(buf[len]); } int main() { int n read(); for (int i 1; i n; i) { a[i] read(); } int top 0; for (int i 1; i n; i) { int last 0; while (top a[st[top]] a[i]) { last st[top]; --top; } if (top) { rc[st[top]] i; } lc[i] last; st[top] i; } for (int i 1; i n; i) { if (i 1) putchar( ); writeInt(lc[i]); } putchar(\n); for (int i 1; i n; i) { if (i 1) putchar( ); writeInt(rc[i]); } putchar(\n); return 0; }代码里最容易被忽略的一行是lc[i] last;它必须在弹栈循环结束之后执行。有人会把它写进 while 循环里导致记录的 last 不是“最后一个被弹出的节点”而是某个中间节点树就挂错了。理解这一步的关键就是我在 2.3 节说的last 是被切下来的右链段中最上层的那个节点它要成为新节点的左孩子而不是把整段链逐个串进去。3.3 快读和快写1e7数据下的生命线在 10^7 数据下不使用快读快写几乎是肯定超时的。scanf和printf虽然方便但每次格式解析都带着额外开销输出 2 千万个数字时差距会被放大到不可接受。我上面的代码用的是基于getchar和putchar的手写 IO。读入函数的核心思路是每次读一个字符跳过非数字再逐位累加。注意(x 3) (x 1)是乘 10 的位运算写法(c ^ 48)等价于c - 0。输出函数则是先把 int 逐位倒序写进一个临时缓冲区再倒序输出。这套组合拳对负数的支持不够但题目输入是 1 到 n 的排列输出也全是非负下标所以够用。如果你以后想把它套用到有负数的题需要额外加符号处理。如果你所在平台时限压得非常紧或者你的机器上putchar感觉偏慢可以把输出改成fwrite批处理先准备一个大缓冲区把所有要输出的字符攒进去再一次fwrite冲刷。核心思想是减少系统调用次数把“写一个字符调一次”变成“攒满一页再调一次”。输入同理也可以用fread分块读。实际竞赛中getchar/putchar版本在绝大多数机器上已经能过 10^7 数据我建议先把逻辑写对再根据实测决定有没有必要上fwrite。4. 常见错误与调试实录4.1 常见问题速查表我踩过、也见别人踩过的坑归纳起来主要是下面这几类。症状可能原因处理方式小数据输出全 0构造时没有把弹出的最后一个节点设为左孩子检查lc[i] last是否在弹栈循环之后某棵子树丢失中序遍历缺节点覆盖右儿子时没理解旧右儿子去了哪里弹出节点最后会进新节点的左子树确认 last 链完整大数据超时用了cin/cout或scanf/printf或者用了递归构造换手写快读快写并用单调栈 O(n) 构造内存超限用了多个 vector或数组开了 MAXN 但没复用只用 a、lc、rc、st 四个 int 数组全开全局静态区输出格式错误少换行或多空格输出循环里空格处理不对每行内部用空格分隔行尾换行不要输出多余空格编译时提示数组太大数组写在了函数内部栈上把数组挪到函数外或者加static4.2 本地验证笛卡尔树的一个小方法大型模板题最怕的不是算法不会而是写完了不知道自己写得对不对。我建议你在本地写一个小型对拍器n 控制在 1000 以内用朴素递归构造实现一份暴力版然后随机生成排列比较两棵树的左右儿子数组是否完全一致。如果你不想写对拍器还有一个更快的自查思路先做一次中序遍历检查输出序列是否等于 1 到 n再逐节点检查 a[父] 是否不大于 a[子]。两个条件同时成立基本可以认定树构造正确。注意在小数据验证时递归中序遍历没问题但 n 很大时千万别用递归否则栈会直接爆掉这也是这道模板题本身强调“别递归”的原因之一。另外说一个调试期很有用的细节构造结束后栈里剩下的元素是整棵笛卡尔树最右链从栈底到栈顶正好是从根到最右下端。你可以顺手打印 st[1] 到 st[top] 检查一下看看链上的权值是否递增。这算是白送的调试工具不用白不用。5. 做完模板之后这把锤子还能敲什么5.1 把区间最值查询变成树上的祖先查询用最小堆版本的笛卡尔树任意区间 [l, r] 的最小值就是节点 l 和节点 r 在树上的最近公共祖先 LCA 的权值。这个性质很漂亮因为 LCA 位于 l 和 r 之间并且根据堆序它的权值不大于子树内的所有节点又因为中序遍历保证子树的连续性所以它就是区间内最小的那个数。这意味着你只要预处理出一棵笛卡尔树就能把经典的 RMQ 问题转化为 LCA 问题。而 LCA 查询可以用倍增、树剖或者转欧拉序 ST 表来做。很多线性 RMQ 的精妙算法底层都是先构造笛卡尔树再在树上做一次 RMQ 或 LCA 的转化。这道模板题虽然只让你输出左右儿子但它本质上给后续这些高级操作准备好了骨架。5.2 直方图最大矩形的单调栈本质力扣或者各种算法题单里那道“柱状图中最大的矩形”很多人都是直接背一个单调栈解法。如果你学过笛卡尔树再看那道题会有一种豁然开朗的感觉单调栈维护的过程本质上就是在动态构建一棵笛卡尔树。在最小堆笛卡尔树里节点 i 的子树在原数组上对应一个连续区间区间边界正好是以 a[i] 为最小值的最大范围。因此“以 a[i] 作为高度的最大矩形宽度”就是节点 i 的子树大小。整道题就变成了建笛卡尔树后序遍历求子树大小然后对所有节点算 a[i] × subtreeSize 取最大值。从“背模板”到“看懂本质”差的往往就是这一层数据结构视角。5.3 顺手理解Treap的“随机堆权”Treap 是很多平衡树实现的底层结构。它的每个节点有一个键值满足 BST 性质还有一个随机的优先级满足堆性质。这个结构本质上就是一棵以键值为下标顺序、以随机优先级为权值的笛卡尔树。因为优先级是随机生成的所以这棵“笛卡尔树”的形态也是随机的期望深度 O(log n)。理解了 P5854 的单调栈建树过程你就能理解 Treap 的 split 和 merge 操作到底在维护什么split 是从某条右链或左链上切一刀merge 是反过来的拼接。很多人学 Treap 觉得玄其实是跳过了笛卡尔树这一层直观模型。除了上面这几个场景笛卡尔树还常用于离线 RMQ 的线性算法、某些分治计数问题、以及后缀数组 height 数组上的区间最小值查询。总之后续用到“区间最小/最大值 位置关系”的地方笛卡尔树都是一个值得优先考虑的基础结构。我个人做完这道模板题后最大的一个体会是别小看单调栈它远不止是“接雨水”的套路。P5854 把单调栈和一个严格定义的二叉树结构焊在一起能让你的算法视角从“操作数组”升级到“维护结构”。以后遇到类似“找左右第一个更小元素”的题先想想是不是可以在构建笛卡尔树的过程中顺手解决。这题的模板我也存到了自己的板子里输出函数和快读部分直接复用到多个大整数输入的数据结构题上性价比很高。如果你想在树形结构上再进一步建议把 LCA 的倍增写法也一并练了配合这道题的产物数据结构的连续题感会很快建立起来。