笛卡尔树
总述
笛卡尔树是一种二叉树，每一个结点由一个键值二元组 \((k,w)\) 构成。要求 \(k\) 满足二叉搜索树的性质，而 \(w\) 满足堆的性质，如果笛卡尔树的 \(k,w\) 键值确定，且 \(k\) 互不相同，\(w\) 互不相同，那么这个笛卡尔树的结构是唯一的，构建的复杂度是\(O(n)\)的
构建
过程
将元素按照键值 \(k\) 排序。然后一个一个插入到当前的笛卡尔树中。那么每次我们插入的元素必然在这个树的右链（右链：即从根结点一直往右子树走，经过的结点形成的链）的末端。于是我们执行这样一个过程，从下往上比较右链结点与当前结点 \(u\) 的 \(w\)，如果找到了一个右链上的结点 \(x\) 满足 \(x_w<u_w\)，就把 \(u\) 接到 \(x\) 的右儿子上，而 \(x\) 原本的右子树就变成 \(u\) 的左子树。
由于每个数最多进出右链一次（或者说每个点在右链中存在的是一段连续的时间）。这个过程我们可以用栈维护，栈中维护当前笛卡尔树的右链上的结点。一个点不在右链上了就把它弹掉。这样每个点最多进出一次，复杂度 \(O(n)\)。
\(ps\) ：\(Treap\) 就是笛卡尔树的一种，只不过 \(w\) 的值完全随机捏~
code
int n,p[N],stk[N],ls[N],rs[N];
il void build(int n){
for(ri int i=1,t=0,tl=0;i<=n;++i,t=tl){
while(t&&p[stk[t]]>p[i]) t--;
if(t) rs[stk[t]]=i;
if(t<tl) ls[i]=stk[t+1];
stk[++t]=i,tl=t;
}
return;
}
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c==45),c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(long long x){
if(x<0) x=-x,putchar(45);
if(x>=10) wt(x/10);
return putchar(x%10|48),void();
}
} using namespace Q;
cs int N=1e7+5;
int n,p[N],stk[N],ls[N],rs[N];
long long las,ras;
il void build(int n){
for(ri int i=1,t=0,tl=0;i<=n;++i,t=tl){
while(t&&p[stk[t]]>p[i]) t--;
if(t) rs[stk[t]]=i;
if(t<tl) ls[i]=stk[t+1];
stk[++t]=i,tl=t;
}
return;
}
signed main(){
n=rd();
for(ri int i=1;i<=n;++i) p[i]=rd();
build(n);
for(ri int i=1;i<=n;++i){
las^=1ll*i*(ls[i]+1);
ras^=1ll*i*(rs[i]+1);
}
wt(las),putchar(32),wt(ras);
return 0;
}