企业官网建设流程全解析

今天打卡信奥刷题第 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] 和 [k+1, 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 入栈，它成为新的最右链端点。

我拿一组小数据走一遍。假设 n=6，a=[4,1,3,2,5,6]：

• i=1，x=4，栈空，lc[1]=0，压栈，栈为 [1]。
• i=2，x=1，a[1]=4>1，弹出 1，last=1，栈空；lc[2]=1，压栈，栈为 [2]。此时 2 成为根，1 是它的左孩子。
• i=3，x=3，a[2]=1<3，不弹；栈顶是 2，rc[2]=3，压栈，栈为 [2,3]。
• i=4，x=2，a[3]=3>2，弹出 3，last=3；此时 a[2]=1<2，停止；栈顶是 2，rc[2]=4，lc[4]=3，压栈，栈为 [2,4]。这一步里 rc[2] 从 3 被覆盖成 4，而 3 变成了 4 的左孩子，正好对应上面说的覆盖规则。
• i=5，x=5，a[4]=2<5，rc[4]=5，压栈，栈为 [2,4,5]。
• i=6，x=6，a[5]=5<6，rc[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++模板：从数组规划到满速IO

3.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 常见问题速查表

我踩过、也见别人踩过的坑，归纳起来主要是下面这几类。

4.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 的倍增写法也一并练了，配合这道题的产物，数据结构的连续题感会很快建立起来。