洛谷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;
}