笛卡尔树

oi-wiki 已讲的足够清晰

顺着思路看下去还是很简单的，我只列出代码展示。

题目链接

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+10;
int n;

int a[N];
int s[N];
int top=1;
int l[N],r[N];
ll ans1,ans2;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;
    
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
	s[1]=1;//只有一个点就放外面了 
    
    for(int i=2;i<=n;i++){
    	while(a[s[top]]>a[i]&&top){//找到第一个小于他的w的点 
    		top--;
		}
		if(!top){//没有说明他最小，他称王 
			l[i]=s[top+1];//前面的点都到左满足二叉搜索树 
		}
		else{
			l[i]=r[s[top]];//值比他大的放下满足堆，放左满足二叉搜索树 
			r[s[top]]=i;//放右要满足二个键对 
		}
		s[++top]=i;//更新链 
	}
    for(int i=1;i<=n;i++){
    	ans1^=((ll)i*(l[i]+1));
    	ans2^=((ll)i*(r[i]+1));
	}
	cout<<ans1<<" "<<ans2;
    return 0;
}