洛谷P5854 【模板】笛卡尔树 题解

题目链接：P5854 【模板】笛卡尔树

题意：

给定一个 $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)$。

数据范围：

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

笛卡尔树的构建非常简单，我们只需要维护一个单调栈即可。

虽然很简单，但是笛卡尔树在一些题目中还是很有用的，原因就在于它可以线性构建。

时间复杂度 $\mathcal{O}(n)$

代码：

// 2024年06月13日 22:24:45
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e7 + 15))

int n, top, a[N], ls[N], rs[N], stk[N];
void build()
{
    for(int i = 1; i <= n; i++)
    {
        int tmp = top;
        while(top > 0 && a[stk[top]] > a[i]) --top;
        if(top > 0) rs[stk[top]] = i; // a[stk[top]] <= a[i]
        if(top < tmp) ls[i] = stk[top + 1]; // a[stk[top + 1]] > a[i]
        stk[++top] = i;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(); ll res1 = 0, res2 = 0;
    for(int i = 1; i <= n; i++)
    {
        res1 ^= (ll)i * (ls[i] + 1);
        res2 ^= (ll)i * (rs[i] + 1);
    }
    cout << res1 << ' ' << res2 << '\n';
    return 0;
}