#C241018E. 【模板】笛卡尔树

标签（Label）

• 笛卡尔树
• 模板

网址（Website）

【模板】笛卡尔树 - 洛谷

练习题： #C241018C. 游客与波特 - WolfDeer

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 10123456;
bool ST;

int n,a[N];

struct Treap{
	int ch[N][2],idx;
	void init(){
		int st[N],tp=0;
		For(i,1,n){
			ch[i][0] = ch[i][1] = 0;
			while(tp && a[st[tp]] > a[i]) ch[i][0]=st[tp--];
			if(tp) ch[st[tp]][1] = i;
			st[++tp] = i;
		}
	}
	void calc(){
		int ans1 = 0, ans2 = 0;
		For(i,1,n){
			ans1 = ans1 ^ (ch[i][0]*i+i);
			ans2 = ans2 ^ (ch[i][1]*i+i);
		}printf("%lld %lld\n",ans1,ans2);
	}
}T;

void Solve(){
	n=rd();For(i,1,n)a[i]=rd();
	T.init();
	T.calc();
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}