P5854 【模板】笛卡尔树
题目描述
给定一个 $1 \sim n$ 的排列 $p$，构建其笛卡尔树。
即构建一棵二叉树，满足：
1. 每个节点的编号满足二叉搜索树的性质。
2. 节点 $i$ 的权值为 $p_i$，每个节点的权值满足小根堆的性质。
输入格式
无
输出格式
无
说明/提示
【样例解释】
| $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$。