题目链接
P5854 【模板】笛卡尔树
题目描述
给定一个 \(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\)。
解题思路
笛卡尔树
笛卡尔树=堆+二叉搜索树
一般对于一个序列建立笛卡尔树，将 \(a[i]\) 建堆的同时将 \(i\) 建二叉搜索树，用栈维护最右链，栈顶元素即最右链最底部的下标，以最小堆为例，对于新插入的节点 \(a[i]\)，找到最右链第一个不大于 \(a[i]\) 的节点 \(j\)，则由最小堆的性质，\(i\) 必须作为 \(j\) 的一个子节点，而还要求下标满足二叉搜索树的性质，\(i\) 应该作为 \(j\) 的右儿子，而原来 \(j\) 的右儿子 \(k\)，\(a[k]>a[i]\)，其应该成为 \(i\) 的左儿子
- 时间复杂度：\(O(n)\)
代码
// Problem: P5854 【模板】笛卡尔树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5854
// Memory Limit: 250 MB
// Time Limit: 500 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
// #define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=1e7+5;
int n,a[N],l[N],r[N];
int stk[N],top;
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
read(a[i]);
int k=top;
while(k>0&&a[stk[k]]>a[i])k--;
if(k)r[stk[k]]=i;
if(k<top)l[i]=stk[k+1];
stk[++k]=i;
top=k;
}
LL L=0,R=0;
for(int i=1;i<=n;i++)
L^=(LL)i*(l[i]+1),R^=(LL)i*(r[i]+1);
printf("%lld %lld",L,R);
return 0;
}