【模板】笛卡尔树

题目描述

给定一个 \(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

提示

【样例解释】

【数据范围】

对于 \(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;
}