P5854 【模板】笛卡尔树

P5854 【模板】笛卡尔树

大意

建一个小根堆笛卡尔树。

思路

用单调栈维护右链，直接建即可。

代码

#include<iostream>
#include<stack>
using namespace std;#define int long long
const int MAXN = 1e7 + 5;
int n, a[MAXN];
int l[MAXN], r[MAXN], in[MAXN];
stack<int> stk;signed main(){ios::sync_with_stdio(0);cin.tie(0);cin >> n;for(int i = 1;i <= n;i ++){cin >> a[i];}stk.push(1);for(int i = 2;i <= n;i ++){int lst = stk.top();while(!stk.empty() && a[i] < a[stk.top()]){lst = stk.top();stk.pop();}if(stk.empty()){l[i] = lst;}else{l[i] = r[stk.top()];r[stk.top()] = i;}stk.push(i);
//		in[l[i]] ++;
//		in[r[i]] ++;}int L = 1 * (l[1] + 1), R = 1 * (r[1] + 1);for(int i = 2;i <= n;i ++){// cout << l[i] << ' ' << r[i] << '\n';L ^= (i * (l[i] + 1)), R ^= (i * (r[i] + 1)); }cout << L << ' ' << R << '\n';return 0;
}