这篇文章有一部分是 2021 年写的，当时完全没有理解笛卡尔树的本质。
笛卡尔树就是最值分治的搜索树。所以最容易的构建笛卡尔树的方式为：
int get(int l,int r){
// 返回 [l,r] 中最值对应的下标
}
void solve(int p,int l,int r){
if(l>=r)return;
solve(lc[p]=get(l,p-1),l,p-1);
solve(rc[p]=get(p+1,r),p+1,r);
}
笛卡尔树的定义
笛卡尔树是一种二叉树，其中的每个节点的权值为 \((p,w)\)。其中，单看权值 \(p\)，这是一棵二叉搜索树。单看权值 \(w\)，这是一个堆。
如果在序列 \(a\) 上建立笛卡尔树，每个点的权值为 \((i,a_i)\)，那么一个节点实际上代表了它子树所覆盖的区间的最值。这是笛卡尔树最常见的性质。
笛卡尔树的建立
上面的构建方法较为常见，用 ST 表维护最值。不过下面的方法更简洁，并且是线性的。
使用一个栈构建笛卡尔树。构建时，需要知道每个点的权值 \((p,w)\)，以 \(p\) 为关键字将点排序，并按顺序将点插入笛卡尔树中。
很明显，一个点插入后，在下一个点插入之前，这个点在这棵树的右链末端，因为此时这个点的 \(p\) 是整棵树中最大的。其中，右链指的是从根节点出发，一直往右走形成的链。
为了维护笛卡尔树的堆性质，我们将右链上的点保存在一个栈中，通过扫描栈的方式决定新加入的点应该插入到哪一个位置。
具体地，设当前栈存储了从当前树的根节点到右链末尾的点。不断弹出栈顶，直至发现栈顶的 \(w\) 值较将要加入的节点小，则此时栈顶可以作为新加入的节点的父亲。这时，我们把栈顶的右子树接在新加入的点的左子树位置上，并把新加入的点作为栈顶的右儿子，新点入栈。
这个过程成功地维护了保存右链的栈，它的时间复杂度是 \(O(n)\)，这是因为每个点至多出入栈分别一次。代码见例题中的模板代码。
笛卡尔树的练习
P5854 【模板】笛卡尔树
板子题，没什么好讲的。对于序列中第 \(i\) 个点，其权值就是 \((i,p_i)\)，所以不需要排序了。
直接放核心代码：
const int N=1e7+5;
int n,a[N],sta[N],l[N],r[N],top;
ll ans1,ans2;
int main(){
IO::rd(n);
for(int i=1;i<=n;i++){
IO::rd(a[i]);
while(top&&a[sta[top]]>a[i])top--;
l[i]=r[sta[top]];//注意这里 r[0] 代表当前的根，所以这样写没有问题。
r[sta[top]]=i;
sta[++top]=i;
}
for(ll i=1;i<=n;i++){
ans1^=i*(l[i]+1);
ans2^=i*(r[i]+1);
}
IO::wt(ans1,' ');IO::wt(ans2,'\n');
return 0;
}
P1377 [TJOI2011]树的序
题意：给定大小为 \(n\) 的一棵 BST 的生成序列，求可以生成同样形态 BST 的字典序最小的生成序列。\(n\le 10^5\)。
思考生成序列对于 BST 形态的影响。可以想到，一个节点在生成序列中的下标总是大于它父亲在生成序列中的下标。也就是这个 BST 在生成序列下标意义下满足小根堆性质。也就是说，这个笛卡尔树中每个点的权值为 \((k_i,i)\)。我们可以通过建立笛卡尔树的方式快速建立这个 BST。
然后我们考虑如何求出最小字典序的生成序列。为了让新的生成序列仍然满足小根堆性质，我们应该在遍历到一个点时，先将这个点加入生成序列末尾。然后因为左子树的键值比较小，先遍历左子树。也就是输出这棵树的先序遍历。
核心代码：
const int N=1e5+5;
int n,val[N],a[N],sta[N],ls[N],rs[N],top;
inline bool cmpA(const int&A,const int&B){
return val[A]<val[B];
}
void dfs(int u){
if(!u)return;
IO::wt(u,' ');
dfs(ls[u]);dfs(rs[u]);
}
int main(){
IO::rd(n);
for(int i=1;i<=n;i++){
IO::rd(val[i]);
a[i]=i;
}
sort(a+1,a+n+1,cmpA);
for(int i=1;i<=n;i++){
while(top&&a[sta[top]]>a[i])top--;
ls[i]=rs[sta[top]];
rs[sta[top]]=i;
sta[++top]=i;
}
dfs(sta[1]);
return 0;
}
SP1805 Largest Rectangle in a Histogram
这是一个单调栈的经典例题，也可以用笛卡尔树做。
刚看到这道题很容易产生一个想法：遍历每一个矩形，把当前矩形高度当成答案矩形高度，并将答案往两边拓展。设当前矩形为 \(u\)，\(L_u=\min\{i\in\mathbb Z\mid \forall j\in[i,u),h_j\ge h_i\}\)，\(R_u=\max\{i\in \mathbb Z\mid \forall j\in (u,i],h_j\ge h_i\}\)。则答案为 \(\max_{u=1}^n \{h_u(R_u-L_u+1)\}\)。
考虑构建一棵节点权值为 \((i,h_i)\) 的笛卡尔树，其中 \(h_i\) 满足小根堆性质。这样一来，对于任意一个点 \(u\) 的子树内的节点 \(v\)，都有 \(h_v\ge h_u\)。
设子树 \(u\) 的大小为 \(\text{siz}_u\)，则答案为 \(\max_{u=1}^n\{h_u\cdot\text{siz}_u\}\)。
核心代码：
const int N=1e5+5;
int n,h[N],sta[N],ls[N],rs[N],siz[N],top;
ll ans;
void dfs(int u){
if(!u)return;
dfs(ls[u]);dfs(rs[u]);
siz[u]=siz[ls[u]]+siz[rs[u]]+1;
ans=max(ans,(ll)h[u]*siz[u]);
}
int main(){
while(1){
IO::rd(n);
if(!n)break;
ans=0;top=0;
for(int i=0;i<=n;i++){//由于 rs[0] 代表根，所以也要清零。
ls[i]=rs[i]=siz[i]=0;
}
for(int i=1;i<=n;i++){
IO::rd(h[i]);
while(top&&h[sta[top]]>=h[i])top--;
ls[i]=rs[sta[top]];
rs[sta[top]]=i;
sta[++top]=i;
}
dfs(sta[1]);
IO::wt(ans,'\n');
}
return 0;
}
CF1748E Yet Another Array Counting Problem
水题，直接在笛卡尔树上跑 DP 就行了。
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
constexpr int N=2e5+5,P=1e9+7;
int n,m,f[N][20],a[N];
inline int ask(int l,int r){
int k=__lg(r-l+1),x=f[l][k],y=f[r-(1<<k)+1][k];
return a[x]>=a[y]?x:y;
}
inline ll add(const ll&x,const ll&y){return (x+y)%P;}
vector<ll>dfs(int l,int r){
if(l==r)return vector<ll>(m,1);
int p=ask(l,r);vector<ll>ret(m),L,R;
if(l<p){
L=dfs(l,p-1);
partial_sum(all(L),L.begin(),add);
}else L=vector<ll>(m,1),ret[0]=1;
if(r>p){
R=dfs(p+1,r);
partial_sum(all(R),R.begin(),add);
}else R=vector<ll>(m,1);
for(int i=1;i<m;i++)ret[i]=L[i-1]*R[i]%P;
ret[0]=ret[0]*R[0]%P;
return ret;
};
inline void ct(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];f[i][0]=i;
}
for(int j=1;j<=__lg(n);j++){
for(int i=1;i+(1<<j)-1<=n;i++){
int x=f[i][j-1],y=f[i+(1<<(j-1))][j-1];
f[i][j]=(a[x]>=a[y]?x:y);
}
}
vector ans=dfs(1,n);
cout<<accumulate(all(ans),0ll,add)<<'\n';
}
int main(){
int T;cin>>T;while(T--)ct();
return 0;
}