在我的心里 NOI 大纲内提高级最难的知识点是圆方树、平衡树和笛卡尔树，平衡树自从自学了 DHQ-treap 后倒是有所改观，今天又重学笛卡尔树，发现貌似并不是那么难（原理上）。看来是我第一次听的时候重视代码而忽略原理了……
笛卡尔树可以定义为：一棵每个节点有 2 个值的二叉树，第一个值为 index（下标），第二个值为 value（数值），而这棵树满足以下限制：
-
value 满足堆性质，即要不然一个节点比其 2 个儿子的 value 值都大（大根堆）要不然比其 2 个儿子的 value 值都小（小根堆）。
-
index 满足二叉搜索树性质，即左儿子的 index 比此节点的 index 小，右儿子的 index 比此节点的 index 大。
先假设我根据给出的一个数组，已经建好了这样一棵树，它能拿来干什么呢？
对于下标为 i 的数，设其左边第一个比它大的数为 \(l_i\)，右边第一个比它大的数为 \(r_i\)，则建立小根堆笛卡尔树，在树上找到这个下标，则 \(l_i\) 为这个下标的左儿子的子树内的最大下标，即先往左走再一直往右走直到没得走，所到达的那个节点的下标。\(r_i\) 同理可得。
我依稀记得有一个特殊性质，就是每个节点的左右子树 Size 较小的一方之和的量级为 \(O(n\log n)\)。我暂时不会证明，以后来补。
如何实现：按照下标，从 \(1\) 到 \(n\) 往笛卡尔树中加入节点。这里默认是建立小根堆笛卡尔树（大根堆只需要变一个符号，大同小异）。
因为下标递增，所以新加入的一定是某个节点的右儿子（或者直接当根），而那个节点之前的右儿子则变成这个节点的左儿子。其它位置则不会发生变化。
考虑到只有可能作为右儿子，所以一定是加在笛卡尔树的右链上（即从根节点一直往右走直到没有右儿子所组成的链）。而由于小根堆性质，右链单调不降，所以可以用一个单调栈维护右链，每次要加入一个节点就在右链上把所有大于其 value 的节点弹出，最后一个被弹出的成为新节点的左儿子（前提是有弹出），若栈里还有元素，则新节点为这个元素的右儿子。
洛谷模板题：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e7+50;
int N;
int p[MAXN];
int ls[MAXN],rs[MAXN];
int sta[MAXN],Top,Now;
long long ans1,ans2;
int Root;
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&p[i]);
Now=Top;
while(Top&&p[sta[Top]]>p[i])
{
Top--;
}
if(Top)
{
rs[sta[Top]]=i;
}
if(Now^Top)
{
ls[i]=sta[Top+1];
}
sta[++Top]=i;
}
for(int i=1;i<=N;i++)
{
ans1^=(1ll*i*(ls[i]+1));
ans2^=(1ll*i*(rs[i]+1));
}
printf("%lld %lld",ans1,ans2);
}