笛卡尔树

笛卡尔树的前序遍历的 \(pos\) 值与原序列相同，且 \(val\) 值构成小根堆。

如何建树：从 \(1\) 到 \(n\) 加节点，用单调栈维护最右链，每次插入时都不断弹出当前栈顶直至栈顶 \(fa\) 满足 \(val[i]>val[fa]\) ，记最后弹出的为 \(j\) ，则 \(fa\) 的右儿子为 \(i\) ，\(i\) 的左儿子为 \(j\).

//5854
#include 
#define int long long
using namespace std;

long long read()
{
	long long res=0,p=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')p=-1; ch=getchar();}
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return res*p;
}

const int maxn=1e7+10;

int n;
int p[maxn];
int a[maxn][2];
long long ansl=0,ansr=0;

vector v;

signed main()
{
	n=read();
	for(int i=1;i<=n;++i) p[i]=read();
	for(int i=1;i<=n;++i)
	{
		int j=0;
		while(v.size()&&p[v.back()]>p[i]) j=v.back(),v.pop_back();
		if(v.size()) a[v.back()][1]=i;
		a[i][0]=j,v.push_back(i);
	}
	for(int i=1;i<=n;++i) ansl^=i*(a[i][0]+1),ansr^=i*(a[i][1]+1);
	cout<