打卡信奥刷题系列走到第2943期今天想认真拆一拆 P5854【模板】笛卡尔树。这道题我拖了很久才动手因为题面简洁得像天书给一个 1 到 n 的排列建一棵笛卡尔树最后输出两个异或和。很多人第一次看题解都会卡住——笛卡尔树到底是什么为什么要用单调栈O(n) 的构造到底在干什么这篇文章把这些一次性讲透代码可以直接抄原理也尽量用大白话解释。适合正在备考 CSP/NOIP 的选手也适合想搞懂 Treap、RMQ 底层关系的学习者。1. 先搞清楚笛卡尔树到底是个什么东西1.1 定义拆开看笛卡尔树的定义一句话就能说清给定序列 a[1..n]构造一棵二叉树使得中序遍历恰好就是原序列的顺序同时每个节点的权值满足堆性质。P5854 里权值就是 a[i]堆性质是小根堆也就是父节点的权值小于子节点。两个约束叠在一起树的结构其实就唯一确定了。这里有个容易误解的地方下标和权值是两个维度。下标决定树的中序顺序权值决定树的祖先关系。可以这样理解把 n 个点 (i, a[i]) 画在坐标平面上横坐标 i 是中序纵坐标 a[i] 是堆序笛卡尔树就是把这些点串成一棵二叉树的自然结果。这个名字并不是随便起的确实和笛卡尔坐标系有关系。题目还保证了输入是一个排列所以权值两两不同不需要考虑相等权值时树不唯一的问题。这个细节后面聊大根堆和等值的时候会再提。1.2 题面真正要求你做什么P5854 的输入是一个长度为 n 的排列输出不是整棵树而是两个异或和lsum Xor(i * (lc[i] 1))rsum Xor(i * (rc[i] 1))其中 lc[i] 表示节点 i 的左儿子编号rc[i] 表示右儿子编号如果没有儿子就记 0。第一次看到这个输出方式的人估计都很疑惑为什么模板题不让我把左右儿子打印出来原因很实际n 最大可以到 10^7如果真让你输出每个节点的左儿子和右儿子光输出就是几千万行评测机大概率直接被打爆。异或和相当于一个压缩校验只要建树时左右关系有一处错最后的值几乎一定对不上。模板题的核心考的是构造过程本身异或输出只是给评测一个快速判定方式。所以这道题的本质非常单纯用尽可能高效的方法把这棵树建出来。而高效的方法就是单调栈O(n) 构造这也是整个模板的灵魂。1.3 什么基础的人适合来打卡如果你只是会递归建树那这道题其实是来“敲打”你的。递归建树在随机数据下看着很美但遇到 n10^7 的模板题时间和空间都会崩。所以这道题特别适合已经会基础树结构、想进阶理解线性复杂度建树技巧的人。如果你是刚接触笛卡尔树的初学者也不用慌。这篇文章会把右链、单调栈、插入操作一个一个拆开讲配一个完整的小例子手推一遍看完再回来看代码就不会觉得那几行是魔法了。2. 单调栈构造O(n) 的原理拆解2.1 为什么朴素做法不行先说说我一开始想到的笨办法每次找到区间最小值作为根然后递归建左右子树。这个思路非常直观因为最小值天然就是小根堆的根中序遍历天然有序看起来完美。问题是效率。最坏情况下序列是单调递增的比如 [1,2,3,4,...,n]每次最小值都在区间最左端递归一层只能劈掉一个节点复杂度直接变成 O(n^2)。而且递归深度会达到 n系统栈想都不用想直接爆掉。n 一旦到 10^7这个方案连跑完输入都费劲。所以模板题的解法只能另找出路。核心洞察在于我们是在按顺序处理下标 i新节点永远是当前已处理序列里下标最大的向左看它一定是整棵树最右侧的节点。这句话是整个算法的基础。2.2 右链是关键什么叫右链从根节点出发一直沿右儿子往下走直到最右下叶子这条路径就是右链。因为父节点的右儿子是子树中下标最小的不是更准确说是最右边的部分所以新节点来了以后只会出现在右链附近。对当前已经建好的前缀 [1..i-1] 来说它的中序遍历是完整的树形态也固定了。这时候插入第 i 个节点由于它的下标最大中序遍历要求它在所有已处理节点的最右边因此它一定落在整棵树的最右侧。换句话说它只会影响右链不会跑去改变左子树里的任何父子关系。这个性质太关键了。它意味着我们不需要重新扫描整棵树只需要维护右链上的节点。右链在任意时刻有多长最多 n但更重要的是右链上的权值是有序的。对于小根堆从根往下父权值小于子权值所以从栈底到栈顶右链节点的权值严格递增。单调栈能派上用场正是因为右链天然满足单调性。2.3 插入一个新节点的三步操作假设现在要插入节点 i权值为 x右链用栈 stk 维护栈底到栈顶对应右链从根到右下。第一步从栈顶开始往栈底方向找弹出所有权值大于 x 的节点。为什么弹因为 x 更小在小根堆里应当更靠近根这些右链上的“大个儿”挡了 x 的路。弹出的过程会停在一个位置 k此时 stk[k] 的权值小于 x或者栈空了。第二步如果 k 不为 0也就是找到了一个权值比 x 小的节点那么节点 i 应该成为 stk[k] 的右儿子。这里要小心理解弹出的那些节点原来是 stk[k] 的右子树沿右链延伸下去现在新节点插在中间所以 stk[k] 的右儿子要改成 i。第三步如果确实弹出了节点k 小于原来的 top那么被弹出的最底下那个节点 stk[k1] 要变成新节点 i 的左儿子。为什么是左儿子因为 stk[k1..top] 这些节点下标都比 i 小中序遍历时它们必须排在 i 前面所以只能放在 i 的左子树里。这一步是最容易绕晕的地方但把中序一摆就清楚了。最后把 i 放到栈的第 k1 个位置右链更新完成。每个节点只会入栈一次、出栈一次均摊 O(1)整棵树的构建就是 O(n)。2.4 拿一个排列完整走一遍光说理论还是抽象我用序列 [4, 2, 5, 1, 3] 手推一遍。这里 a[i] 同时是权值也是题目给的排列值节点编号就是下标。当前节点权值弹出情况关键动作操作后的栈栈底→栈顶14无入栈[1]22弹出 1lc[2] 1[2]35无rc[2] 3[2, 3]41弹出 3、2lc[4] 2[4]53无rc[4] 5[4, 5]得到的树长这样根是 4 号节点左儿子是 2 号右儿子是 5 号2 号的左儿子是 1 号右儿子是 3 号。仔细检查一遍中序遍历从 4 号开始左子树 2 号下又有左 1 和右 3然后 4 号再右子树 5 号顺序是 1-2-3-4-5对应原序列 [4,2,5,1,3]完全正确。堆性质也满足4 号权值 1 小于 2 号权值 2 和 5 号权值 32 号权值 2 小于 1 号权值 4 和 3 号权值 5。这张表值得自己动手再走一遍走通了基本就懂单调栈了。3. 完整代码与关键细节3.1 可以直接抄的代码下面是一份可以提交的完整代码同时包含了建树和异或和输出。#include bits/stdc.h using namespace std; const int MAXN 10000005; int a[MAXN], lc[MAXN], rc[MAXN], stk[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; } 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 k top; while (k a[stk[k]] a[i]) --k; if (k) rc[stk[k]] i; if (k top) lc[i] stk[k 1]; stk[k] i; top k; } long long ansL 0, ansR 0; for (int i 1; i n; i) { ansL ^ 1LL * i * (lc[i] 1); ansR ^ 1LL * i * (rc[i] 1); } printf(%lld %lld\n, ansL, ansR); return 0; }这份代码看起来短但浓缩了上面所有原理。拆开看每一行都很简单。3.2 那个 k top 的小技巧核心建树只有五句最难理解的是int k top开头、最后stk[k] i; top k;收尾的写法。这不是开了一个新栈而是直接复用栈数组用 k 在原来的栈上做局部修改。相当于把原来的栈想象成右链从顶往下“回卷”。while 循环里--k就是在逻辑上弹出节点弹出的部分不会被真正清空而是留在 stk[k1..top] 里。随后if (k top) lc[i] stk[k 1]正是从这些“废弃区”里取出最后弹出的那个节点。最后新节点写到 k1 位置top 更新为 k右链就无缝切换了。整个过程没有开新数组没有移动元素时间复杂度 O(1) 均摊常数很小。我第一次看这个写法时觉得像魔术后来自己模拟了几遍才意识到它其实就是把一个“将要被丢弃”的区间保留了最后一次引用并把它挂到新节点的左儿子上。这就是整个算法最精妙的部分。3.3 内存、读入和输出的实战细节先读入全部 a 再建树是为了在 while 里能直接通过a[stk[k]]拿到栈顶权值。这个写法最直观内存需要 a、lc、rc、stk 四个 int 数组每个大约 40MBn10^7总共约 160MB绝大多数评测环境没问题。如果遇到内存卡得严的平台可以改成边读边建省掉对 a 的依赖但需要额外开一个数组存栈中节点的权值数组总数并不会少只是少了一次全数组遍历的常数时间int main() { int n read(); int top 0; for (int i 1; i n; i) { int x read(); int k top; while (k val[stk[k]] x) --k; if (k) rc[stk[k]] i; if (k top) lc[i] stk[k 1]; stk[k] i; val[k] x; top k; } // 输出部分与上面相同 }读入方面n 到 10^7 时输入量非常大手写快读是值得的。(x 3) (x 1)就是乘 10(c ^ 48)等价于 c - 0编译器通常也能优化到位。考试环境中如果不想手写关掉同步的 cin 也勉强能用但既然模板题建议直接养成快读的习惯。输出用%lld因为后面异或式子里有乘法具体原因下面会说明。4. 常见问题与避坑记录4.1 递归建树为什么在这里必死我觉得这个坑值得单独说。递归建树思路清晰代码也短但有两个致命问题一是最坏 O(n^2)二是递归深度 O(n)。n 是 10^7 时就算递归不爆栈时间复杂度也不可能通过。模板题就是要你放弃递归转到单调栈迭代解法。如果是在别的题里遇到笛卡尔树且 n 较小比如 n 10^5递归建树勉强能跑但高频任务最好还是统一用单调栈版本不用根据数据规模换写法。4.2 左右儿子被覆盖不是 bug是设计新手在模拟时会发现一个现象某个节点的右儿子在后续操作中可能会被改成新节点。比如第 2 步里 rc[2] 先被设为 3到第 4 步插入 4 号节点时2 号节点的右儿子又被“让位”给了 4不对仔细看模拟过程2 号节点的右儿子最后是 3没变。但另一种情况下确实会覆盖当节点 stk[k] 的原右子树整体被新节点截断时stk[k] 的右儿子会从原来的 stk[k1] 改成新节点 i而原来的 stk[k1] 变成 i 的左儿子。这不是错误正是中序和堆性质共同作用的结果。写代码的时候不用担心覆盖顺序问题只要按照模板里if (k) rc[stk[k]] i;在前、if (k top) lc[i] stk[k 1];在后的顺序写就行。每棵子树只被移动一次不会丢节点。4.3 大根堆和等值权值怎么改P5854 默认是小根堆建堆条件是弹出栈中权值大于新节点的节点也就是 while 里写a[stk[k]] a[i]。如果题目换成大根堆只需要把大于号换成小于号while (k a[stk[k]] a[i]) --k;意思是把权值比新节点小的都弹掉让大的靠近根。等值的情况要额外注意。题目输入是排列所以代码里不需要处理相等但如果你拿这道题的模板去解决实际问题序列里可能出现重复权值。重复权值下笛卡尔树不唯一必须根据需求决定相等时挂哪边。一种常见做法是把严格大于改成大于等于使后出现的等值节点更靠近根另一种是保持严格大于让先出现的节点在上。选哪种取决于你后续要用树做什么操作。直接套模板遇到重复值很容易挂。4.4 异或和为什么必须用 long long看这一行ansL ^ 1LL * i * (lc[i] 1);。n 最大是 10^7i 接近 10^7lc[i] 1 也可能是 10^7 级别乘积就是 10^14 上下远远超过 int 的 21 亿上限。如果不写 1LLi * (lc[i] 1) 先按 int 计算溢出后再异或答案铁定错。lc、rc、a、stk 这些数组本身用 int 够但进入乘法必须转 long long这是一个很容易踩但一眼就能看出来的坑。另一个细节是“空儿子 1”的写法lc[i] 是 0 时乘积是 i * 1 i相当于把空儿子也计入校验。如果题目改成输出完整树空儿子位置要按题面要求处理这里纯粹是题目定义。4.5 全局数组与栈空间的取舍数组开全局区是最稳妥的做法。试试把 a、lc、rc、stk 开在 main 函数内部n 是 10^7 时四个数组就是 160MB局部变量会占用系统栈空间大概率直接段错误。全局区没有这个问题默认清零还省了初始化。数组大小建议开 MAXN n 上限 5 左右宁可多开几个 int也別卡着边界开。数据刚好到上限时边界处的访问是 UB在本地可能没事在评测机上说不定就 RE 了。5. 笛卡尔树建好之后能干什么5.1 离线 RMQ区间最值变 LCA笛卡尔树一个非常漂亮的用途是解决静态区间最值问题。对一个小根堆笛卡尔树任意区间 [l, r] 的最小值恰好等于节点 l 和节点 r 的最近公共祖先LCA对应的权值。这是因为 lca(l, r) 的子树正好覆盖了从 l 到 r 的所有节点而在小根堆里祖先的权值是子树中最小的。有了这个性质配合 Tarjan 离线 LCA 或者欧拉序 ST 表就能把区间最小值问题转换成树上问题。当然竞赛中求 RMQ 更多会直接写 ST 表或线段树但笛卡尔树的思路经常在一些压轴题中出现理解它相当于多了一把钥匙。5.2 最大矩形面积那道单调栈经典题的本质LeetCode 84 直方图最大矩形POJ 2559 也是同一道题很多人做过单调栈版本但没意识到标准的单调栈解法本质上就是在建一棵笛卡尔树。直方图的每个柱子对应一个节点柱子的高度就是权值。建出小根堆笛卡尔树后每个节点能作为顶边的最大矩形宽度就是它作为根时子树覆盖的区间宽度。对每个节点算一遍“高度 × 区间宽度”取最大值答案就出来了。所以学这道模板题并不只是背一个算法它顺手把另一类常见的单调栈题也串起来了。以后再遇到这类题脑子里可以同时浮现出单调栈和笛卡尔树两条路径很多题是互相转换的。5.3 Treap随机化的笛卡尔树Treap 这个名字就是 Tree Heap 的合成词。它每个节点除了 BST 的键值还有一个随机优先级并要求优先级满足堆性质。把这个定义和笛卡尔树对比一下键值就是下标或者有序键优先级就是权值。Treap 本质上就是一棵随机优先级生成的笛卡尔树。理解了笛卡尔树的单调栈构造再去看 Treap 的旋转、merge、split会有一种“原来如此”的感觉。Treap 之所以期望平衡是因为随机优先级让笛卡尔树的期望高度是 O(log n)这也解释了为什么随机化数据结构能稳定高效。模板题只要求建树但上层应用才是笛卡尔树真正值钱的地方。结尾说点实操体会细想下来这个模板真正难的地方不在代码而在于一个认知转变新节点只会动右链而右链是一根天然单调的链。基于这一点单调栈不是“优化技巧”而是顺着数据结构性质长出来的自然解法。我自己第一次看见k top那份五行建树代码时完全没看懂后来把一个例子在纸上画了三棵树的右链才真正转过弯来。如果你现在也在这一关上卡着建议别急着背代码先拿题面的例子手推一遍再把 while 循环对应到右链的每一步变化上你会发现它其实非常简单。日常训练时也别忘了把这个模板的变体大根堆、等值处理、边读边建都写一遍考场上遇到才不慌。