## 题目链接
[this](https://www.luogu.com.cn/problem/P5854)
># P5854 【模板】笛卡尔树
>
>## 题目描述
>
>给定一个1 \sim n 的排列p，构建其笛卡尔树。
>
>即构建一棵二叉树，满足：
>
>1. 每个节点的编号满足二叉搜索树的性质。
>2. 节点i 的权值为p_i，每个节点的权值满足小根堆的性质。
>
>## 输入格式
>
>第一行一个整数n。
>
>第二行一个排列p_{1 \dots n}。
>
>## 输出格式
>
>设l_i,r_i 分别表示节点i 的左右儿子的编号（若不存在则为0）。
>
>一行两个整数，分别表示\operatorname{xor}_{i = 1}^n i \times (l_i + 1) 和\operatorname{xor}_{i = 1}^n i \times (r_i + 1)。
>
>## 输入输出样例 #1
>
>### 输入 #1
>
>```
>5
>4 1 3 2 5
>```
>
>### 输出 #1
>
>```
>19 21
>```
>
>## 说明/提示
>
>【样例解释】
>
>|i |l_i |r_i |
>| :-: | :-: | :-: |
>|1 |0 |0 |
>|2 |1 |4 |
>|3 |0 |0 |
>|4 |3 |5 |
>|5 |0 |0 |
>
>【数据范围】
>
>对于30\% 的数据，$n \le 10^3$。
>
>对于60\% 的数据，$n \le 10^5$。
>
>对于80\% 的数据，$n \le 10^6$。
>
>对于90\% 的数据，$n \le 5 \times 10^6$。
>
>对于100\% 的数据，$1 \le n \le 10^7$。
## 题目分析
本题要求构建一个笛卡尔树，满足：
- BST性质：节点编号满足二叉搜索树性质（中序遍历为1,2, ...,n）
- 小根堆性质：节点权值满足小根堆性质（父节点权值≤ 子节点权值）
## 算法思路 ###
单调栈构建法
使用单调栈在O(n) 时间内构建笛卡尔树。
核心思想是维护一个**单调递增栈**，栈中存储的是从根到最右节点的路径（右链）。
### 构建过程
按照节点编号1 到n 的顺序逐个插入节点：
1. 弹栈操作：弹出栈中所有权值大于p[i] 的节点
- 这些节点由于小根堆性质，不能成为节点i 的祖先
- 记录最后一个弹出的节点lst
2. 建立父子关系：
- 若栈不为空，节点i 成为栈顶的右儿子
- 若lst 存在，它成为节点i 的左儿子
3. 入栈：将节点i 压入栈中
## 代码实现
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL read() {
LL x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-') f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void write(LL x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int MAXN = 1e7 + 5;
LL p[MAXN], L[MAXN], R[MAXN], stk[MAXN], top;
int main() {
int N = read();
// 读入权值数组
for (int i = 1; i <= N; ++i) {
p[i] = read();
}
// 单调栈构建笛卡尔树
for (int i = 1; i <= N; ++i) {
int lst = 0;
// 弹出所有权值大于 p[i] 的节点
while(top > 0 && p[stk[top]] > p[i])
lst = stk[top--];
// i 成为栈顶的右儿子
if (top > 0)
R[stk[top]] = i;
// 最后弹出的节点成为 i 的左儿子
if (lst > 0)
L[i] = lst;
// 将 i 压入栈
stk[++top] = i;
}
// 计算答案
LL ans1 = 0, ans2 = 0;
for (int i = 1; i <= N; ++i) {
ans1 ^= i * (L[i] + 1);
ans2 ^= i * (R[i] + 1);
}
write(ans1), putchar(' '), write(ans2);
return 0;
}
```
## 算法详解
### 为什么这样构建是正确的？
1. BST性质保证：由于我们按照1 到n 的顺序插入，每个新节点都在当前树的最右侧，保证了中序遍历的顺序。
2. 小根堆性质保证：通过弹栈操作，确保栈中维护的是一条权值单调递增的路径，从而保证了小根堆性质。
### 样例模拟
以样例p = [4, 1, 3, 2, 5] 为例：
| 步骤 | 操作 | 栈状态 | 左儿子 | 右儿子 |
|------|------|--------|--------|--------|
|i = 1 | 压入1 |[1] |L[1] = 0 |- |
|i = 2 | 弹出1，压入2 |[2] |L[2] = 1 |R[2] = ? |
|i = 3 | 压入3 |[2,3] |L[3] = 0 |R[2] = 3 |
|i = 4 | 弹出3，压入4 |[2,4] |L[4] = 3 |R[2] = 4 |
|i = 5 | 压入5 |[2,4,5] |L[5] = 0 |R[4] = 5 |
最终树结构：
```
2(权值1)
/ \
1 4(权值2)
/ \
3 5
```
## 复杂度分析
- 时间复杂度： $O(n)$
- 每个节点最多入栈一次、出栈一次
- 总操作次数为O(n) - 空间复杂度： $O(n)$
- 需要存储权值数组、左右儿子数组和栈
## 总结
单调栈构建笛卡尔树是一个经典算法，通过维护右链的单调性，巧妙地在线性时间内完成了树的构建。这种方法不仅高效，而且代码简洁优雅，是处理大规模数据的必选方案。
