【模板】笛卡尔树
题目描述
给定一个 \(1 \sim n\) 的排列 \(p\),构建其笛卡尔树。
即构建一棵二叉树,满足:
- 每个节点的编号满足二叉搜索树的性质。
- 节点 \(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\)。
知识
笛卡尔树是一种特定的二叉树,可由数列数列构造,在范围最值查询、范围top k查询(range top k queries)等问题上有广泛应用。它具有堆的有序性,中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成,需要采用基于栈的算法来找到在该数列中的所有最近小数。
笛卡尔树每一个结点由一个二元组\((k,v)\)构成。k是键值,v是优先级,要求\(k\)满足二叉搜索树的性质,而\(v\)满足堆的性质。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e7 + 10;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
int n, a[N], ls[N], rs[N];
int s[N], top;//单调栈维护当前树中最右链
int main() {
n = read();
for (int i = 1; i <= n; i ++) a[i] = read();
s[top = 1] = 1;
for (int i = 2; i <= n; i ++) {
while (a[i] < a[s[top]] && top) ls[i] = s[top --];//栈顶元素为当前元素的左儿子
if (top) rs[s[top]] = i;//当前元素为栈顶元素的右儿子
s[++ top] = i;
}
ll ans1 = 0, ans2 = 0;
for (int i = 1; i <= n; i ++) {
ans1 ^= (1ll * i * (ls[i] + 1));
ans2 ^= (1ll * i * (rs[i] + 1));
}
cout << ans1 << " " << ans2 << '\n';
return 0;
}