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手推一遍就清楚了。这里括号里是下标(值)栈按从左到右表示从栈底到栈顶。处理节点新值弹栈过程last连边操作栈内状态14无0直接入栈1(4)21弹出 1(4)1栈空节点2成为新根节点1作为节点2左儿子2(1)33不弹1 30节点2右儿子设为节点32(1), 3(3)42弹出 3(3)3节点2右儿子设为节点4节点3作为节点4左儿子2(1), 4(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 手工栈的迭代遍历最通用的替代方案是把递归改成手动模拟栈。拿最常见的“中序/后序统计子树”举例可以用两个栈模拟后序遍历vectorint order; stackint 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、直方图问题就都串起来了。如果你也在打卡刷题建议先别急着交代码亲手把样例的栈变化画一遍哪怕只画一组数据也比直接看十篇题解有用得多。