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

题目链接：https://www.luogu.com.cn/problem/P5854

笛卡尔树 模板题。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 5;int n;struct Node {int s[2], p, pri;
} tr[maxn];void f_s(int p, int u, int k) {tr[p].s[k] = u;tr[u].p = p;
}void build_tree() {stack<int> stk;stk.push(0);for (int i = 1; i <= n; i++) {int pos = stk.top();while (!stk.empty() && tr[stk.top()].pri > tr[i].pri) {pos = tr[stk.top()].p;stk.pop();}f_s(i, tr[pos].s[1], 0);f_s(pos, i, 1);stk.push(i);}
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &tr[i].pri);build_tree();long long res1 = 0, res2 = 0;for (int i = 1; i <= n; i++) {res1 ^= 1ll * i * (tr[i].s[0] + 1);res2 ^= 1ll * i * (tr[i].s[1] + 1);}printf("%lld %lld\n", res1, res2);return 0;
}