题目链接

this

P5854 【模板】笛卡尔树

题目描述

给定一个 的排列，构建其笛卡尔树。

即构建一棵二叉树，满足：

1. 每个节点的编号满足二叉搜索树的性质。
2. 节点 的权值为，每个节点的权值满足小根堆的性质。

输入格式

第一行一个整数。

第二行一个排列。

输出格式

设 分别表示节点 的左右儿子的编号（若不存在则为）。

一行两个整数，分别表示 和。

输入输出样例 #1

输入 #1

```

5

4 1 3 2 5

```

输出 #1

```

19 21

```

说明/提示

【样例解释】

| | | |

| :-: | :-: | :-: |

| | | |

| | | |

| | | |

| | | |

| | | |

【数据范围】

对于 的数据，$n \le 10^3$。

对于 的数据，$n \le 10^5$。

对于 的数据，$n \le 10^6$。

对于 的数据，$n \le 5 \times 10^6$。

对于 的数据，$1 \le n \le 10^7$。

题目分析

本题要求构建一个笛卡尔树，满足：

• BST性质：节点编号满足二叉搜索树性质（中序遍历为,, ...,）
• 小根堆性质：节点权值满足小根堆性质（父节点权值 子节点权值）

算法思路

单调栈构建法

使用单调栈在 时间内构建笛卡尔树。

核心思想是维护一个 ** 单调递增栈 **，栈中存储的是从根到最右节点的路径（右链）。

构建过程

按照节点编号 到 的顺序逐个插入节点：

1. 弹栈操作：弹出栈中所有权值大于 的节点

• 这些节点由于小根堆性质，不能成为节点 的祖先
• 记录最后一个弹出的节点

2. 建立父子关系：

• 若栈不为空，节点 成为栈顶的右儿子
• 若 存在，它成为节点 的左儿子

3. 入栈：将节点 压入栈中

代码实现

```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性质保证：由于我们按照 到 的顺序插入，每个新节点都在当前树的最右侧，保证了中序遍历的顺序。
2. 小根堆性质保证：通过弹栈操作，确保栈中维护的是一条权值单调递增的路径，从而保证了小根堆性质。

样例模拟

以样例 为例：

| 步骤 | 操作 | 栈状态 | 左儿子 | 右儿子 |

|------|------|--------|--------|--------|

| | 压入 | | | |

| | 弹出，压入 | | | |

| | 压入 | | | |

| | 弹出，压入 | | | |

| | 压入 | | | |

最终树结构：

```

2(权值 1)

   / \\

  1   4(权值2)

     / \\

    3   5

```

复杂度分析

• 时间复杂度：O(n)
• 每个节点最多入栈一次、出栈一次
• 总操作次数为 - 空间复杂度： $O(n)$
• 需要存储权值数组、左右儿子数组和栈

总结

单调栈构建笛卡尔树是一个经典算法，通过维护右链的单调性，巧妙地在线性时间内完成了树的构建。这种方法不仅高效，而且代码简洁优雅，是处理大规模数据的必选方案。