题解
笛卡尔树的定义如下:任意一颗子树都代表一段连续的区间,且子树的根节点是该区间的最大值,根的左边的元素下标均比根小(二叉搜索树性质),子节点均比父节点大(堆的性质)
我们讲如何实现的
设即将要插入的元素为 \(a_i\)
栈内的元素为前 \(i-1\) 个元素构成的笛卡尔树从根一直走右节点途径的节点(途径顺序为从栈底到栈顶)
如果 \(a_i\) 比栈顶元素小,则 \(r[st.top()]=i\),然后压入栈内
否则找到从栈底到栈顶最后一个比自己小的元素 \(x\),令 \(x\) 后面的第一个元素变成 \(a_i\) 的左子节点(剩余元素全部弹出,顺序不变),\(x\) 的右节点变为 \(a_i\) 然后压入栈内
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[10000007], l[10000007] = {0}, r[10000007] = {0};
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n;
cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
stack<ll> q;
for (ll i = 1; i <= n; i++)
{
if (q.empty()) q.push(i);
else
{
ll tem = 0;
while (q.size() && a[q.top()] >= a[i])
{
tem = q.top();
q.pop();
}
l[i] = tem;
if (q.size()) r[q.top()] = i;
q.push(i);
}
}
ll ans1 = 0, ans2 = 0;
for (ll i = 1; i <= n; i++)
{
ans1 ^= i * (l[i] + 1);
ans2 ^= i * (r[i] + 1);
}
cout << ans1 << " " << ans2;
return 0;
}
标签:P5854,10000007,笛卡尔,ll,元素,top,节点,模板
From: https://www.cnblogs.com/pure4knowledge/p/18284201