笛卡尔树基本概念
笛卡尔树是基于一个静态序列 \(a\) 的，根据这个序列 \(a\)，我们可以构造出对应的笛卡尔树。
笛卡尔树有三点要求需要满足：
-
笛卡尔树是二叉树。
-
笛卡尔树的编号的中序遍历为 \(1\sim n\)，权值中序遍历为 \(a\)。
-
笛卡尔树的权值满足大根堆或者小根堆的性质。
这里可以看一个图，节点上标的是权值。
为了更加方便，笛卡尔树的节点编号与序列 \(a\) 的下标编号共用。
笛卡尔树的构造
这里我们先给出笛卡尔树的性质：
-
对于树上一条深度单调递增的路径，其权值单调不减。
-
\(\forall u,v;u\le v;p=\operatorname{lca}(u,v)=p\)，以 \(p\) 为根的子树恰好涵盖 \(a\) 序列中 \([u,v]\) 区间的所有位置。
-
\(\forall u,v;u\le v;p=\operatorname{lca}(u,v)=p\)，其在笛卡尔树上的最近公共祖先的权值 \(val_p\) 恰好为 \(a\) 序列中 \([u,v]\) 区间的最小值。
于是我们可以在线性时空内构造笛卡尔树。
我们考虑维护笛卡尔树上最右端的链，则有这条链的编号和权值都不减，于是我们可以用单调栈维护。
我们从前向后遍历 \(a\) 数组，设当前的位置为 \(i\)，同时前 \(i-1\) 位的笛卡尔树已经构建完成，于是我们假设当前栈顶位置 \(top\)，则当前栈顶元素为 \(s_{top}\)，然后我们进行分类讨论。
-
\(a_i\ge a_{s_{top}}\)，直接将 \(i\) 入栈。事实上就是在笛卡尔树的最右端的最下面插入这个元素。
-
否则，开始弹出栈，直到栈为空或者栈顶元素权值不小于 \(a_i\)，这里设最后一个弹出的元素的下标设为 \(j\)。则把 \(i\) 入栈，\(j\) 变为 \(i\) 的左儿子。
这里再挂个图，方便理解：
然后我们就建完树了，可以开始看题了。
笛卡尔树
考虑直接按照上面的步骤建树，维护一下左右儿子即可，没有需要特别注意的地方，所以直接放一下代码：
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 10000005
using namespace std;
int n,a[N],stk[N],rt,res1,res2;
pii w[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int top=0,cur=0;
for(int i=1;i<=n;i++){
cur=top;
while(top&&a[stk[cur]]>a[i])cur--;//弹栈
if(cur)w[stk[cur]].y=i;//没弹完代表有东西更小，作为右儿子
if(cur<top)w[i].x=stk[cur+1];//有东西出栈了，把出栈的最后一个节点作为当前点左儿子
stk[++cur]=i;//入栈
top=cur;
}
for(int i=1;i<=n;i++){
res1^=(i*(w[i].x+1));
res2^=(i*(w[i].y+1));
}
cout<<res1<<' '<<res2;
return 0;
}
树的序
类似于板子，说了这么多，其实就是对笛卡尔树求一个前序遍历，所以直接上代码：
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 10000005
using namespace std;
int n,a[N],stk[N],rt,res1,res2;
pii w[N];
void dfs(int u){
if(u==0)return;
cout<<u<<' ';
dfs(w[u].x);
dfs(w[u].y);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[x]=i;
}
int top=0,cur=0;
for(int i=1;i<=n;i++){
cur=top;
while(top&&a[stk[cur]]>a[i])cur--;
if(cur)w[stk[cur]].y=i;
if(cur<top)w[i].x=stk[cur+1];
stk[++cur]=i;
top=cur;
}
dfs(stk[1]);
return 0;
}