企业官网建设流程全解析

打卡信奥刷题系列走到第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 什么基础的人适合来打卡

如果你只是会递归建树，那这道题其实是来“敲打”你的。递归建树在随机数据下看着很美，但遇到 n=10^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[k+1] 要变成新节点 i 的左儿子。为什么是左儿子？因为 stk[k+1..top] 这些节点下标都比 i 小，中序遍历时它们必须排在 i 前面，所以只能放在 i 的左子树里。这一步是最容易绕晕的地方，但把中序一摆就清楚了。

最后，把 i 放到栈的第 k+1 个位置，右链更新完成。每个节点只会入栈一次、出栈一次，均摊 O(1)，整棵树的构建就是 O(n)。

2.4 拿一个排列完整走一遍

光说理论还是抽象，我用序列 [4, 2, 5, 1, 3] 手推一遍。这里 a[i] 同时是权值，也是题目给的排列值，节点编号就是下标。

得到的树长这样：根是 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 号权值 3；2 号权值 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[k+1..top] 里。随后if (k < top) lc[i] = stk[k + 1]正是从这些“废弃区”里取出最后弹出的那个节点。最后新节点写到 k+1 位置，top 更新为 k，右链就无缝切换了。整个过程没有开新数组，没有移动元素，时间复杂度 O(1) 均摊，常数很小。

我第一次看这个写法时觉得像魔术，后来自己模拟了几遍才意识到，它其实就是把一个“将要被丢弃”的区间保留了最后一次引用，并把它挂到新节点的左儿子上。这就是整个算法最精妙的部分。

3.3 内存、读入和输出的实战细节

先读入全部 a 再建树，是为了在 while 里能直接通过a[stk[k]]拿到栈顶权值。这个写法最直观，内存需要 a、lc、rc、stk 四个 int 数组，每个大约 40MB（n=10^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[k+1] 改成新节点 i，而原来的 stk[k+1] 变成 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^7，i 接近 10^7，lc[i] + 1 也可能是 10^7 级别，乘积就是 10^14 上下，远远超过 int 的 21 亿上限。如果不写 1LL，i * (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 循环对应到右链的每一步变化上，你会发现它其实非常简单。日常训练时也别忘了把这个模板的变体（大根堆、等值处理、边读边建）都写一遍，考场上遇到才不慌。