【数据结构】【模板】笛卡尔树

笛卡尔树

定义

笛卡尔树每个节点有两种属性，一种是键值，一种是优先级。

一般将位置作为键值，维护 BST 的性质，这样其中序遍历一定为 \(1 ~ n\)。

一般将数值看作优先级，维护堆的性质。

构建思路

维护一个单调栈，表示现在的右链长度。

我们将数组从前往后插入笛卡尔树。

对于第 \(i\) 个数，我们将比其大的数字从栈顶弹出，将 \(i\) 接在栈顶元素的右儿子上，将刚刚弹出的元素接在左儿子上（不破坏其结构）。

代码

P5854 代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 10000010;

int n, a[N];
int lc[N], rc[N];
int stk[N], top;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        int k = top;
        while (k && a[stk[k]] > a[i]) k--;
        if (k) rc[stk[k]] = i;
        if (k < top) lc[i] = stk[k + 1];
        stk[++k] = i;
        top = k;
    }

    i64 ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; i++) {
        ans1 = ans1 ^ (1ll * i * (lc[i] + 1));
        ans2 = ans2 ^ (1ll * i * (rc[i] + 1));
    }
    cout << ans1 << ' ' << ans2 << '\n';
    return 0;
}