笛卡尔树

#include<cstdio>
#define INT 10000007
typedef long long ll;
struct dtree{
	int ls=0,rs=0;
	int d1,d2;
}tr[INT];
int n;
void build(){
	int now=0,top=0;
	int stk[INT];
	for (int i = 1; i <= n; ++i)
	{
		now=top;
		while(now&&tr[i].d2<tr[stk[now]].d2)now--;//右链上的第一个符合位置
		top=now+1;
		stk[top]=i;
		tr[i].ls=tr[stk[now]].rs;
		tr[stk[now]].rs=i;
	}
}
int main(){
	
	scanf("%d",&n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d",&tr[i].d2);
		tr[i].d1=i;
	}
	build();
	ll ans1=0,ans2=0;
	for (int i = 1; i <= n; ++i)
	{
		//printf("%d %d\n",tr[i].ls,tr[i].rs);
		ans1^=1ll*i*(tr[i].ls+1);
		ans2^=1ll*i*(tr[i].rs+1);
	}
	printf("%lld %lld",ans1,ans2);
}