企业官网建设流程全解析

P5854这道模板题，我刷题打卡的时候卡了一整个晚上。不是题目本身有多绕，而是大部分资料讲笛卡尔树的时候，都喜欢直接丢结论：单调栈维护最右链，弹栈、接左子树、入栈，听起来十二个字就完了。真到自己动手写，三个数组怎么填、弹出的节点到底接到哪里、栈底是不是树根，全都能混成一锅粥。这篇博客就把我从“背模板”到“能推模板”的完整过程复述一遍，顺便把提交时真正会踩的坑都摊开讲，适合刚接触笛卡尔树的读者，也适合那些会背代码但说不清原理的人。

1. 题目到底在问什么：建一棵键值按下标、优先级按值的树

1.1 一种容易混淆的结构

笛卡尔树这名字听着高端，拆开看就是一棵同时满足两套规则的二叉树：

• 中序遍历结果是原序列的下标顺序，也就是1, 2, 3, ..., n。你可以把它理解为“下标构成了一棵二叉搜索树”。
• 每个节点带一个值，整棵树满足堆性质。P5854里给的是一个小根堆规则：任意节点的值都小于等于它子树里所有节点的值。

这两套规则叠在一起，树的形态就是唯一的。有个特别直观的构造方式：在一段连续的序列里找出最小值，让它当根，最小值左边的数递归建左子树，右边的数递归建右子树。这样建出来的东西，天然就满足“左边下标都比根小，右边下标都比根大”，而且根的值一定是区间里最小的。

这个递归定义看起来很漂亮，但它没法直接拿来做题。每次找区间最小值要扫描，递归下去就是O(n log n)甚至更差，数据一大直接报废。模板题需要的是一遍扫描O(n)建树，于是才有了后面要讲的单调栈做法。

1.2 这道模板题要求的输出

P5854的输入是一个n和一个1到n的排列。输出是三行整数：

• 第一行：每个节点的父节点编号，没有父节点输出0。
• 第二行：每个节点的左儿子编号，没有左儿子输出0。
• 第三行：每个节点的右儿子编号，没有右儿子输出0。

所以代码里最少要准备三个数组：fa、lc、rc。再算上存值的val数组和单调栈用的st数组，一共五个int数组。这个内存账要提前算清楚，后面我会专门说。

这里强调一下，题目输入是排列，排列表明所有值两两不同，树的形态不会产生歧义。如果后面自己拿笛卡尔树处理非排列数据，就得额外规定值相等时的优先级，这一点在第5章会细说。

2. 为什么非用单调栈不可

2.1 暴力插入的复杂度瓶颈

如果不知道单调栈，最容易想到的方法是：按顺序把每个节点插入现有树里。问题是插到哪里？因为下标必须满足中序遍历，新来的节点下标是当前最大的，它只能出现在整棵树最右侧的某条路径上。从一个根出发，一路往右儿子走，找到第一个值比新节点大的节点，把新节点接到它前面。

问题是，这个“找”的过程如果每次沿着右链走一遍，遇到递增序列1 2 3 ... n的时候，树会退化成一条只有右儿子的链，每次插入都要走到链尾，总复杂度变成O(n²)。数据到10^7根本跑不完。

2.2 最右链的性质

解决这个问题的钥匙，是维护“当前已经建好的树的最右链”。所谓最右链，就是从根开始，一路只走右儿子，直到没有右儿子为止。这条链上每个节点的左子树都已经完整建好，不再受后续节点影响。

当一个新的节点i到来时，它只会影响最右链。原因很朴素：新节点下标最大，在中序遍历中排在最后，它不可能成为某个已有节点的左子树里的节点，只可能出现在整棵树最右侧。所以建树过程可以看成“不断往最右链里插入新节点”。

单调栈里存的就是这条最右链上的节点，栈底是根，栈顶是最右链的末端。同时栈内的值从栈底到栈顶是递增的。这一点可以这样理解：沿最右链从上往下走，因为越往下越“新”，而新节点总会被放到第一个值比它大的节点上方，所以链上的值确实越往下越大。

2.3 一镜到底：用排列 4 1 3 2 走一遍

光说理论容易晕，拿样例4 1 3 2手推一遍就清楚了。这里括号里是下标(值)，栈按从左到右表示从栈底到栈顶。

最终树的形态：根是节点2，左儿子是节点1，右儿子是节点4，节点4的左儿子是节点3。对应的输出就是：

• 父节点：2 0 4 2
• 左儿子：0 1 0 3
• 右儿子：0 4 0 0

这里面最核心的动作是第4步：弹出节点3之后，不能直接把节点4接上去就完事，还要把最后弹出的节点3变成节点4的左儿子。因为节点3原本是节点2的右儿子，现在节点4要插在节点2和节点3中间，而节点3又必须保持中序遍历在节点4之后，所以它只能成为节点4的左子树。这就是单调栈建树里最容易绕晕的一步。

3. C++实现：核心建树部分的每一行取舍

3.1 建树主循环

建树主循环只有十来行，但每一行都值得掰开讲：

for (int i = 1; i <= n; ++i) { int last = 0; while (top > 0 && val[st[top]] > val[i]) { last = st[top]; --top; } if (top > 0) { rc[st[top]] = i; fa[i] = st[top]; } if (last != 0) { lc[i] = last; fa[last] = i; } st[++top] = i; }

last变量必须每一轮重新置0，它记录的是“最后一个被弹出的节点”。这个节点是整个弹出集合里最靠右、也是值最大的那个，下一步要作为新节点的左儿子。

while的弹出条件用val[st[top]] > val[i]，比较的是“值”，不是下标。很多人初写时容易写成st[top] > i，结果整个树都建错。

弹完之后分两种情况：

• 栈里还有节点，说明当前节点要挂在某个右链节点下面。因为栈顶是目前右链上值小于val[i]的最近节点，所以rc[st[top]] = i。
• last非零，说明刚才有一段右链被拆下来了，整段要作为i的左子树。注意这里不是只连一个节点，last作为这段链中最后一个被弹出的节点，它自己原本就带着一串左子树和右子树，所以只需把它接到i的左儿子位置即可。

最后无论有没有弹出，i都要入栈。因为i现在是整棵树最右侧的节点，最右链的末端一定是它。

3.2 完整可交的模板代码

如果只写建树逻辑，用scanf和printf在数据量小的时候没问题。但 P5854 这类模板题经常把n开到10^7，既要读n个数进去，又要输出3n个整数，scanf加printf很容易被 IO 卡掉。所以完整代码里我习惯直接上fread快读和fwrite快写：

#include <bits/stdc++.h> using namespace std; const int MAXN = 10000005; int val[MAXN], lc[MAXN], rc[MAXN], fa[MAXN], st[MAXN]; int top; namespace FastIO { const int BUFSIZE = 1 << 20; char ibuf[BUFSIZE], *iS = ibuf, *iT = ibuf; char obuf[BUFSIZE], *oS = obuf; inline char gc() { if (iS == iT) { iT = (iS = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); if (iS == iT) return EOF; } return *iS++; } inline int read() { int x = 0; char c = gc(); while (c < '0' || c > '9') c = gc(); while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); } return x; } inline void flush() { fwrite(obuf, 1, oS - obuf, stdout); } inline void pc(char c) { if (oS == obuf + BUFSIZE) { fwrite(obuf, 1, BUFSIZE, stdout); oS = obuf; } *oS++ = c; } inline void writeInt(int x) { if (x > 9) writeInt(x / 10); pc(char(x % 10 + '0')); } } int main() { using namespace FastIO; int n = read(); for (int i = 1; i <= n; ++i) val[i] = read(); for (int i = 1; i <= n; ++i) { int last = 0; while (top > 0 && val[st[top]] > val[i]) { last = st[top]; --top; } if (top > 0) { rc[st[top]] = i; fa[i] = st[top]; } if (last != 0) { lc[i] = last; fa[last] = i; } st[++top] = i; } for (int i = 1; i <= n; ++i) { writeInt(fa[i]); pc(' '); } pc('\n'); for (int i = 1; i <= n; ++i) { writeInt(lc[i]); pc(' '); } pc('\n'); for (int i = 1; i <= n; ++i) { writeInt(rc[i]); pc(' '); } pc('\n'); flush(); return 0; }

writeInt我用了递归，但这里数字最多10^7，十进制不超过8位，递归深度可忽略。输出行的末尾多一个空格，绝大多数评测系统不会计较，如果实在不放心，可以把每行最后一个数字后面的空格改成不输出，但没必要为了这个增加分支复杂度。

3.3 复杂度与空间

时间复杂度是严格的O(n)。每个节点入栈一次、出栈最多一次，每次弹栈都对应一条边的调整，所以整个主循环是线性的。加上读写，总复杂度不会超过O(n)，这也是笛卡尔树模板题能被放到10^7数据规模的原因。

空间上要注意：val、lc、rc、fa、st五个int数组，n = 10^7时约5 * 4 * 10^7 = 200MB。题目一般会给足够的内存，但如果你在别的平台上遇到内存限制很紧的情况，要提前评估。所有树结构数组和栈数组都省不掉，因为它们各自都有独立用途，没有互相覆盖的可能。

4. 递归输出的隐患与三种替代方案

4.1 树退化成链时的递归灾难

P5854本身只要求输出三个数组，建完树直接循环输出就行，不需要递归遍历。但实际比赛里，题目往往是建完笛卡尔树之后还要做子树统计、区间查询之类的操作，这时候大家第一反应就是写个递归DFS。

问题来了：笛卡尔树在极端数据下会退化成长链。比如输入序列严格递增1 2 3 ... n，建出来的树就是一条深度为n的右链。如果用递归DFS，默认栈帧根本扛不住，轻则爆栈，重则直接段错误。我就见过有人建树成功，却在DFS环节被RE打得一头雾水。

4.2 手工栈的迭代遍历

最通用的替代方案是把递归改成手动模拟栈。拿最常见的“中序/后序统计子树”举例，可以用两个栈模拟后序遍历：

vector<int> order; stack<int> stk; stk.push(root); while (!stk.empty()) { int u = stk.top(); stk.pop(); if (u == 0) continue; order.push_back(u); stk.push(lc[u]); stk.push(rc[u]); } reverse(order.begin(), order.end());

这是先序顺序压栈，最后翻转得到后序。拿到后序顺序后，就可以从后往前逐节点把子树信息合并给父亲。不用递归，栈上最多只保留一条右链的量，空间反而更稳。

4.3 借助堆序性质直接统计子树信息

还有一个更妙的思路，能完全绕开遍历。笛卡尔树的小根堆性质是：父节点的值一定小于子节点的值。而题目输入又是排列，值从1到n各出现一次。

那么求每个节点的子树大小，可以直接按值从大到小处理：

for (int i = 1; i <= n; ++i) sz[i] = 1; for (int v = n; v >= 1; --v) { if (fa[v] != 0) sz[fa[v]] += sz[v]; }

因为值大的节点一定是某个值更小的节点的后代，按值逆序处理时，每个节点都会把自己的子树大小先累加给父亲，等轮到父亲时，它的所有儿子都已经算好了。这个过程完全不需要DFS，也不需要知道左儿子右儿子，只要fa数组在手就行。这个技巧在笛卡尔树相关的子树统计题里非常实用，强烈建议记下来。

5. 最容易翻车的五个细节

5.1 下标和值的比较混用

建树时比较的是val[st[top]] > val[i]，这决定了小根堆的形态。如果错写成st[top] > i，把所有下标比较当成了值比较，那棵树会变成一头四不像。尤其当你把节点编号和节点值都用int存时，这种错误肉眼很难发现，必须自己拿样例手推一遍才能定位。

我的习惯是：写循环时故意把变量名区分开，st里存的是“节点编号”，val[节点编号]才是“比较用的值”。如果代码里出现连续两次st[top]，我都会停下来确认，这一下到底是想要编号还是要值。

5.2 最后弹出的节点丢失

这是最常见的WA原因。last必须在每轮循环开始前重置为0，然后在while里不断更新。如果只在弹出前声明last = st[top]而不更新，最后拿到的是第一次弹出的节点，而不是最后一次弹出的节点。

要理解为什么必须取“最后”弹出的节点：弹出操作是从右链末端往根的方向连续弹出的，最先弹出的节点是最下端、最靠近新节点的，它可能已经带着一大堆右链结构。真正需要接到新节点左子树的，是这段被弹出链的“链头”，也就是最后弹出的那个。取错了，树的形状就会乱掉。

5.3 赋值左右子树的时机

rc[st[top]] = i和lc[i] = last这两步的顺序可以互换，但心里必须清楚它们各自的前提：

• rc[st[top]] = i只有在栈非空时才执行，当前节点接在某个已有节点的右儿子位置。
• lc[i] = last只有在last != 0时才执行，说明新节点确实顶替了一段右链。

有一种看似正确但会错得很隐蔽的写法：先把last接到i的左儿子，再把i接到栈顶右儿子，然后在last存在时把fa[last]更新成i。顺序写反可能导致某次赋值被后续覆盖。我建议代码里按“先右儿子，再左儿子”的固定顺序写，和单调栈的推导过程保持一致，不容易乱。

5.4 输出格式与边界

输出三行情这一块，最容易出问题的是行末换行和行内空格。我见过有人只输出两行换行，第三行忘记pc('\n')，结果答案最后一整行粘连到下一题的输出里。虽然这类模板题通常不涉及多组数据，但习惯必须养成，每行结束都明确输出换行符。

边界情况更要单测：n = 1时，三个数组全是0，栈里只有节点1，必须保证程序不越界、能输出三行0。很多人写for (int i = 1; i <= n; ++i)遍历没问题，但如果在输出前用了st[1]取根，n = 1时也要确认栈底确实是根。

5.5 有重复键值时的处理

模板题给的是排列，所以不用担心相等情况。但把笛卡尔树搬到现实数据里，很可能出现两个节点的值相等。这时必须定义比较规则，否则堆性质不再严格。

一种通用做法是给每个节点加一个“次级优先级”。比如要求值小优先，值相等按下标小的优先，那么弹出条件可以写成：

while (top > 0 && (val[st[top]] > val[i] || (val[st[top]] == val[i] && st[top] > i))) { last = st[top]; --top; }

这样即使值相等，也能通过下标做二次比较，保证树形态唯一、堆性质严格成立。如果你只是做练习题，可能用不上这个，但刷题经验多了之后你会发现，很多题目给的所谓“序列”根本不会保证完全互异，提前想好tie-breaker能省很多debug时间。

6. 模板之外：笛卡尔树还能派什么用场

6.1 RMQ的离线解法

笛卡尔树最经典的应用之一是把区间最值问题转化成树上问题。建出小根笛卡尔树后，区间[l, r]的最小值，恰好就是节点l和节点r在树上的最近公共祖先对应节点的值。

原因在于中序遍历按下标排布，区间[l, r]在原序列中是一段连续下标，它们在笛卡尔树里对应的最小公共祖先，就是包含这个区间的最小值点。有了这个性质，离线询问可以用最近公共祖先的算法解决，预处理O(n)，单次询问做到O(log n)甚至O(1)，比线段树在某些约束下更轻巧。

6.2 与Treap的关系

Treap 的完整名字本来就是“Tree + Heap”，它给每个节点随机分配一个优先级，然后按“二叉搜索树键值 + 堆优先级”的方式组织。笛卡尔树本质上就是 Treap 去掉随机部分、优先级由题目给定的结果。

所以学会笛卡尔树的单调栈建树，再去看 Treap 的分裂合并，会有一种豁然开朗的感觉：Treap 按优先级满足堆性质，笛卡尔树也按值满足堆性质；Treap 的旋转或者分裂合并，本质上都在维护这个“堆套 BST”的结构。很多选手是先背 Treap 再学笛卡尔树，会觉得难；反过来先吃透笛卡尔树再学 Treap，会顺畅很多。

6.3 直方图最大矩形

直方图最大矩形是一道非常经典的栈题，它还有一个笛卡尔树视角。把每个柱子的高度作为节点值，下标作为中序键值建小根笛卡尔树。以某个柱子为矩形高度的最大扩展范围，正好是它的左子树大小加右子树大小再加自己，对应数组上一个连续区间。

于是建树之后，只需要一遍后序统计子树大小，就能O(n)求出每个柱子作为高度的最大矩形面积，再取最大值。这道题和 P5854 的代码有大量重合，你一旦把模板吃透，再遇到那些所谓“进阶题”，会发现很多只是笛卡尔树套了一层业务外壳。

说句实在话，P5854 的代码就算死记硬背下来也不难，但真正把单调栈和最右链的关系想通之后，后续遇到的 RMQ、Treap、直方图问题就都串起来了。如果你也在打卡刷题，建议先别急着交代码，亲手把样例的栈变化画一遍，哪怕只画一组数据，也比直接看十篇题解有用得多。