浅谈笛卡尔树

2026-08-24 11:31:03

发布于：北京

12阅读

0回复

0点赞

笛卡尔树

笛卡尔树，是对 $n$ 个键值对 $(k,w)$ 建出的一种特殊的树。具体地，在这棵树里， $k$ 值满足二叉搜索树的性质（左儿子小于根小于右儿子）， $w$ 满足堆的性质。在一般题目中，我们将序列下标设为 $k$ ，序列值设为 $w$ 。

图片

笛卡尔树的性质，就是二叉搜索树的性质加上堆的性质。

构建

假设我们的堆是小根堆。我们考虑按照 $k$ 从小到大构建（也就是从左往右构建），显然对于第 $i$ 个，它一定是目前键最大的，因此它一定是在最右边的。那么，它就肯定不会出现在某个节点的左子树上（因为根据二叉搜索树性质，点的左子树都在点左侧）。于是，我们考虑维护笛卡尔树的右链。对于 $i$ ，我们先将它假设为右链底端的点 $t$ 的右儿子，然后只要 $a_i<a_t$ ，就一步步上浮，最终上浮到不能再上浮。此时， $i$ 下面那个点就是 $i$ 的左儿子， $i$ 上面那个点的右儿子就是 $i$ 。我们发现，一个点被上浮过，就再也不在右链上了，因此可以使用单调栈维护。时间复杂度是 $O(n)$ 。

伪代码：

for i=1 to n:
	while stack is not empty and a[stack.top()]>a[i]:
		stack.pop()
	if stack is not empty:
		rightson[stack.top()]=i
	if stack has popped:
		leftson[i]=last pop

例题

P5854 【模板】笛卡尔树

板子题，不讲了。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e7+17;
struct node{
    int l,r;
};
int n,top,ttop;
ll ans1,ans2;
int a[MAXN],stk[MAXN];
node cart[MAXN];
inline void read(int &x){
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++){
        ttop=top;
        while(ttop&&a[i]<a[stk[ttop]]) ttop--;
        if(ttop) cart[stk[ttop]].r=i;
        if(ttop<top) cart[i].l=stk[ttop+1];
        top=ttop;
        stk[++top]=i;
    }
    for(int i=1;i<=n;i++){
        ans1^=i*(cart[i].l+1ll);
        ans2^=i*(cart[i].r+1ll);
    }
    cout<<ans1<<' '<<ans2;
    return 0;
}

P1377 [TJOI2011] 树的序

先手玩一下样例，容易发现其实答案就是搜索树的前序遍历，证明也很显然。所以这个题的复杂度瓶颈在于求搜索树，可以考虑使用笛卡尔树。题目描述里的键值 $k$ 对应到笛卡尔树板子里应该是下标，所以我们令 $a_{k_i}=i$ ，然后对 $a$ 数组建笛卡尔树即可。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+15;
struct cartree{
    ll l,r;
};
ll n,k,top,ttop,rt;
ll a[MAXN],stk[MAXN];
cartree cart[MAXN];
void dfs(const ll &u){
    cout<<u<<' ';
    if(cart[u].l) dfs(cart[u].l);
    if(cart[u].r) dfs(cart[u].r);
    return;
}
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>k;
        a[k]=i;
    }
    for(ll i=1;i<=n;i++){
        ttop=top;
        while(ttop&&a[stk[ttop]]>a[i]) ttop--;
        if(ttop) cart[stk[ttop]].r=i;
        if(ttop<top) cart[i].l=stk[ttop+1];
        top=ttop;
        stk[++top]=i;
    }
    rt=stk[1];
    dfs(rt);
    return 0;
}

Largest Rectangle in a Histogram

考虑对于一个区间 $[l,r]$ 的答案，容易发现，如果设其最小值为 $m$ ，答案是 $m(r-l+1)$ 。把这个直方图拍到笛卡尔树上，相当于对于一个点 $u$ ，它子树内有 $siz_u$ 个点，那么这个 $u$ 的贡献是 $siz_uh_u$ ，因为笛卡尔树的性质保证了 $h_u$ 是整个子树内的最小值，所以这样是对的。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+15;
struct cartree{
	ll l,r;
	cartree(const ll &A=0,const ll &B=0):l(A),r(B){}
};
ll n,top,ttop,rt,ans;
ll a[MAXN],stk[MAXN],siz[MAXN];
cartree cart[MAXN];
void dfs(const ll &u){
	siz[u]=1;
	if(cart[u].l){
		dfs(cart[u].l);
		siz[u]+=siz[cart[u].l];
	}
	if(cart[u].r){
		dfs(cart[u].r);
		siz[u]+=siz[cart[u].r];
	}
	ans=max(siz[u]*a[u],ans);
	return;
}
void solve(){
	top=ans=0;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		cart[i]=cartree();
	}
	for(ll i=1;i<=n;i++){
		ttop=top;
		while(ttop&&a[stk[ttop]]>a[i]) ttop--;
		if(ttop) cart[stk[ttop]].r=i;
		if(ttop<top) cart[i].l=stk[ttop+1];
		top=ttop;
		stk[++top]=i;
	}
	rt=stk[1];
	dfs(rt);
	cout<<ans<<'\n';
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while(true){
		cin>>n;
		if(n==0) break;
		solve();
	}
	return 0;
}

CF1220F Gardener Alex

首先我们考虑对于每一种排列的笛卡尔树是什么样的。它的根一定是 $a_m=1$ 的 $i$ 。如果我们令 $b=\left[a_{m+1},a_{m+2},\dots,a_n,a_1,a_2,\dots,a_{m-1}\right]$ ，那么 $m$ 的左子树就是 $b$ 的一段后缀，右子树是 $b$ 的一段前缀。设左子树最大深度为 $d_1$ ，右子树为 $d_2$ ，答案就是 $\max(d_1,d_2)+1$ 。

容易发现后缀其实是和前缀求法一样的，因此我们先只考虑前缀怎么做，再复制一遍就是后缀求法了。

可以设 $dep_u$ 表示点 $u$ 的深度， $maxd_u$ 表示 $u$ 子树内最大的深度。考虑笛卡尔树构建过程中的每一个操作会对这些值产生什么影响。当我们 pop 一个元素 $T$ 时，相当于将其下沉一格，也就是 $dep_{T}\gets dep_{T}+1,maxd_{T}\gets maxd_{T}+1$ 。当 $T$ 的右儿子设为 $i$ 的时候，我们可以求出 $dep_i=dep_{T}+1$ 。如果 $i$ 上浮到根，则 $dep_i=1$ 。同时我们可以知道 $maxd_i=dep_i$ 。当 $i$ 的左儿子设为 $T$ 的时候，我们就可以更新 $maxd$ 了。也就是 $chkmax(maxd,maxx)$ ，其中 $maxx$ 是前面 pop 掉的所有元素里的最大 $maxd$ 值。进行完这些操作之后，我们发现可以利用 $maxd_i$ 去更新它的父亲的 $maxd$ 了。前缀最大深度 $pre_i$ 一开始等于 $pre_{i-1}$ ，后面每更新一次 $maxd$ ，也要同时更新一下 $pre_i$ 。

然后最后求左移次数，假设 $pre_i+suf_{i+1}=ans$ ，那么说明 $a_m$ 右侧有 $i$ 个点，因此左移次数为 $(i+m)\bmod n$ 。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25;
struct cartree{
    ll ls,rs;
    cartree(const ll &A=0,const ll &B=0):ls(A),rs(B){}
};
ll n,m,top,ttop,rt,maxx,ans=1e18;
ll a[MAXN],b[MAXN],stk[MAXN],dep[MAXN],maxd[MAXN],pre[MAXN],suf[MAXN];
cartree cart[MAXN];
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>a[i];
    for(ll i=1;i<=n;i++){
        if(a[i]==1){
            m=i;
            for(ll j=1;j<n;j++) b[j]=a[(j+i-1)%n+1];
            break;
        }
    }
    for(ll i=1;i<n;i++){
        pre[i]=pre[i-1];
        ttop=top;
        maxx=0;
        while(ttop&&b[stk[ttop]]>b[i]){
            maxx=max(++maxd[stk[ttop]],maxx);
            dep[stk[ttop]]++;
            ttop--;
        }
        pre[i]=max(maxx,pre[i]);
        if(ttop){
            cart[stk[ttop]].rs=i;
            dep[i]=dep[stk[ttop]]+1;
        }
        else dep[i]=1;
        maxd[i]=dep[i];
        pre[i]=max(dep[i],pre[i]);
        if(ttop<top){
            cart[i].ls=stk[ttop+1];
            maxd[i]=max(maxx,maxd[i]);
        }
        if(ttop){
            maxd[stk[ttop]]=max(maxd[i],maxd[stk[ttop]]);
            pre[i]=max(maxd[stk[ttop]],pre[i]);
        }
        top=ttop;
        stk[++top]=i;
    }
    top=0;
    for(ll i=1;i<n;i++) cart[i]=cartree();
    memset(dep,0,sizeof(dep));
    memset(maxd,0,sizeof(maxd));
    for(ll i=n-1;i;i--){
        suf[i]=suf[i+1];
        ttop=top;
        maxx=0;
        while(ttop&&b[stk[ttop]]>b[i]){
            maxx=max(++maxd[stk[ttop]],maxx);
            dep[stk[ttop]]++;
            ttop--;
        }
        suf[i]=max(maxx,suf[i]);
        if(ttop){
            cart[stk[ttop]].rs=i;
            dep[i]=dep[stk[ttop]]+1;
        }
        else dep[i]=1;
        maxd[i]=dep[i];
        suf[i]=max(dep[i],suf[i]);
        if(ttop<top){
            cart[i].ls=stk[ttop+1];
            maxd[i]=max(maxx,maxd[i]);
        }
        if(ttop){
            maxd[stk[ttop]]=max(maxd[i],maxd[stk[ttop]]);
            suf[i]=max(maxd[stk[ttop]],suf[i]);
        }
        top=ttop;
        stk[++top]=i;
    }
    for(ll i=0;i<n;i++) ans=min(max(pre[i],suf[i+1])+1,ans);
    // for(ll i=1;i<n;i++) cout<<pre[i]<<' ';
    // cout<<endl;
    // for(ll i=1;i<n;i++) cout<<suf[i]<<' ';
    // cout<<endl;
    cout<<ans<<' ';
    for(ll i=0;i<n;i++){
        if(max(pre[i],suf[i+1])+1==ans){
            cout<<(i+m)%n;
            return 0;
        }
    }
    return 0;
}

P6453 [COCI 2008/2009 #4] PERIODNI

观察题目给的图片，发现中间断开导致的合法情况，其实相当于在笛卡尔树中处于两个不同子树内。考虑树形 DP。

首先我们设 $a_u=h_u-h_{fa_u}$ 。令 $f_{u,i}$ 表示在 $u$ 的子树内放置 $i$ 个方案数， $g_{u,i}$ 表示在 $u$ 子树内（不包括 $u$ ）放 $i$ 个的方案数。

然后我们发现，儿子与父亲其实是有下面一部分重叠的部分的（大小为 $h_{fa}$ ），非常不好处理，所以我们定义点 $u$ 上，能放置的位置只有 $a_u$ 个，而不是 $h_u$ 。

考虑转移， $f_{u,i}$ 可以先在儿子上放 $i-j$ 个，再在下面一大堆重叠部分放 $j$ 个。下面重叠的是一个矩形形状。如果笛卡尔树上点 $u$ 管辖区间是 $[l_u,r_u]$ ，那么这个矩形的长宽就分别是： $r_u-l_u+1,a_u$ 。但是，由于我们需要在儿子上放置 $i-j$ 个，所以矩形有 $i-j$ 列不能放了，所以实际的长宽是 $r_u-l_u+1-(i-j),a_u$ 。我们需要在这个矩形里放 $j$ 个且没有同行同列。首先我们选择 $j$ 列，方案数 $\binom{r_u-l_u+1-(i-j)}{j}$ ；然后我们选择 $j$ 行，方案数 $\binom{a_u}{j}$ 。这样我们就确定了 $j$ 个点。但是呢，这 $j$ 个点的行列换一下位置，其实是不同的方案，所以要再乘一个 $j!$ 。

$g_{u,i}$ 是比较简单的，应该是 $\sum f_{ls_u,j}f_{rs_u,i-j}$ 。

总转移就长这样：

$g_{u,i}=\sum_{j=0}^i f_{ls_u,j}f_{rs_u,i-j} \\ f_{u,i}=\sum_{j=0}^i g_{u,i-j}\binom{r_u-l_u+1-i+j}{j}\binom{a_u}{j}j!$

边界比较简单：

$f_{u,0}=1 \\ f_{u,1}=a_u \\ g_{u,0}=1 \\ f_{0,0}=1$

时间复杂度： $O(n^3)$ 。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1e9+7;
struct cartree{
    ll ls,rs,fa,l,r;
};
ll n,k,top,ttop,rt;
ll h[505],a[505],stk[505],fact[1000005],invfac[1000005],f[505][505],g[505][505];
cartree cart[505];
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
void init(){
    fact[0]=1;
    for(ll i=1;i<=1000000;i++) fact[i]=i*fact[i-1]%MOD;
    invfac[1000000]=qpow(fact[1000000],MOD-2);
    for(ll i=1000000;i;i--) invfac[i-1]=i*invfac[i]%MOD;
    return;
}
ll C(const ll &n,const ll &m){
    if(n<m||m<0) return 0;
    return fact[n]*invfac[m]%MOD*invfac[n-m]%MOD;
}
void dfs(const ll &u){
    a[u]=h[u]-h[cart[u].fa];
    if(cart[u].ls) dfs(cart[u].ls);
    if(cart[u].rs) dfs(cart[u].rs);
    if(!cart[u].ls&&!cart[u].rs){
        f[u][0]=g[u][0]=1,f[u][1]=a[u];
        return;
    }
    ll len=cart[u].r-cart[u].l+1;
    for(ll i=0;i<=min(k,len);i++) for(ll j=0;j<=i;j++) g[u][i]=(g[u][i]+f[cart[u].ls][j]*f[cart[u].rs][i-j]%MOD)%MOD;
    for(ll i=0;i<=min(k,len);i++) for(ll j=0;j<=i;j++) f[u][i]=(f[u][i]+g[u][i-j]*C(len-i+j,j)%MOD*C(a[u],j)%MOD*fact[j]%MOD)%MOD;
    return;
}
int main(){
    init();
    cin>>n>>k;
    for(ll i=1;i<=n;i++) cin>>h[i];
    for(ll i=1;i<=n;i++){
        cart[i].l=cart[i].r=i;
        ttop=top;
        while(ttop&&h[stk[ttop]]>h[i]){
            cart[stk[ttop]].r=i-1;
            ttop--;
        }
        if(ttop){
            cart[stk[ttop]].rs=i;
            cart[i].fa=stk[ttop];
        }
        if(ttop<top){
            cart[i].ls=stk[ttop+1];
            cart[stk[ttop+1]].fa=i;
            cart[i].l=cart[stk[ttop+1]].l;
        }
        top=ttop;
        stk[++top]=i;
    }
    rt=stk[1];
    for(ll i=1;i<=top;i++) cart[stk[i]].r=n;
    f[0][0]=1;
    dfs(rt);
    cout<<f[rt][k];
    return 0;
}

P5654 基础函数练习题

首先这个 $F(l,r)$ 其实就是对于区间 $[l,r]$ 建立大根笛卡尔树，然后查询从 $\operatorname{LCA}(l,r)$ 向下走，到一个儿子数量 $<2$ 的点的最大点权和。

设 $t=\operatorname{LCA}(l,r)$ ，则有：

$F(l,r)=\max\left(F(l,t-1),F(t+1,r)\right)+w_t$

考虑把两边分别算出来，这样 $l,r$ 的两个限制就会变成一个限制。容易发现第二项和第一项是对称的，所以我们只考虑怎么算 $F(l,t-1)$ 。

显然所有的答案都是发生在 $\geq l$ 的位置的，所以我们从 $l$ 开始向上跳（只往右跳），这样肯定覆盖所有答案。至于为什么只往右跳，考虑笛卡尔树性质可以得知， $u$ 的右子树所有点一定 $>u$ ，而 $l$ 的祖先的子树肯定有 $l$ 这个点，因此如果 $u$ 在 $l$ 的左侧，那 $u<l$ 是必然的。

那么既然向左的父亲没用，我们不妨直接扔掉吧。设 $u$ 的右儿子是 $rs$ ，则定义 $fa_{rs}=fa_u$ 即可。

重定义父亲后就可以正常让 $l$ 向上跳了。考虑 $l$ 点的答案怎么算。首先， $l$ 的右子树肯定是可以参与计算的（都 $>l$ ，提前预处理即可），然后再求一个 $dist(l,t)$ 加进去就行。这个暴力做是 $O(n)$ 的。

我们直接考虑倍增，令 $fa_{u,i}$ 表示 $u$ 向上走 $2^i$ 步的点（当然，是重定义之后的父亲）， $ju_{u,i}$ 表示从 $u$ 向上走 $2^i-1$ 步经过的点权和， $res_{u,i}$ 表示当 $l=u,t=fa_{u,i}$ 时的答案。

转移如下：

$fa_{u,i}=fa_{fa_{u,i-1},i-1} \\ ju_{u,i}=ju_{u,i-1}+ju_{fa_{u,i-1},i-1} \\ res_{u,i}=\max(res_{fa_{u,i-1},i-1},res_{u,i-1}+ju_{fa_{u,i-1},i-1})$

当处理 $F(t+1,r)$ 的时候，只需要再次重定义 $fa$ 即可。

然后我们注意到老牧师出题人只给开 250 MB 大小，哦不不不我无疑是愤怒的，所以要节约一些数组，把倍增数组循环利用一下。显然离线询问下来把两边分别放一块算就能节约一半。

时间复杂度： $O(n \log n)$ 。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=5e5+5;
struct cartree{
    int ls,rs;
};
int n,q,top,ttop,rt;
int p[MAXN],w[MAXN],dep[MAXN],stk[MAXN],l[MAXN],r[MAXN],t[MAXN],fa[MAXN][19];
ll f[MAXN],ans[MAXN],ju[MAXN][19],res[MAXN][19];
cartree cart[MAXN];
void dfs1(const int &u,const int &fath){
    fa[u][0]=fath;
    dep[u]=dep[fath]+1;
    for(int i=1;i<19;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    if(cart[u].ls) dfs1(cart[u].ls,u);
    if(cart[u].rs) dfs1(cart[u].rs,u);
    f[u]=max(f[cart[u].ls],f[cart[u].rs])+w[u];
    return;
}
void dfs2(const int &u){
    ju[u][0]=w[u];
    res[u][0]=w[u]+f[cart[u].rs];
    for(int i=1;i<19&&fa[u][i-1];i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
        ju[u][i]=ju[u][i-1]+ju[fa[u][i-1]][i-1];
        res[u][i]=max(res[fa[u][i-1]][i-1],res[u][i-1]+ju[fa[u][i-1]][i-1]);
    }
    if(cart[u].ls){
        fa[cart[u].ls][0]=u;
        dfs2(cart[u].ls);
    }
    if(cart[u].rs){
        fa[cart[u].rs][0]=fa[u][0];
        dfs2(cart[u].rs);
    }
    return;
}
void dfs3(const int &u){
    ju[u][0]=w[u];
    res[u][0]=w[u]+f[cart[u].ls];
    for(int i=1;i<19&&fa[u][i-1];i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
        ju[u][i]=ju[u][i-1]+ju[fa[u][i-1]][i-1];
        res[u][i]=max(res[fa[u][i-1]][i-1],res[u][i-1]+ju[fa[u][i-1]][i-1]);
    }
    if(cart[u].ls){
        fa[cart[u].ls][0]=fa[u][0];
        dfs3(cart[u].ls);
    }
    if(cart[u].rs){
        fa[cart[u].rs][0]=u;
        dfs3(cart[u].rs);
    }
    return;
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=18;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=18;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
ll calc(int u,const int &v){
    ll ret=0;
    for(int i=18;i>=0;i--){
        if(dep[fa[u][i]]>=dep[v]){
            ret=max(ret+ju[u][i],res[u][i]);
            u=fa[u][i];
        }
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=n;i++){
        ttop=top;
        while(ttop&&p[stk[ttop]]<p[i]) ttop--;
        if(ttop) cart[stk[ttop]].rs=i;
        if(ttop<top) cart[i].ls=stk[ttop+1];
        top=ttop;
        stk[++top]=i;
    }
    rt=stk[1];
    dfs1(rt,0);
    for(int i=1;i<=q;i++){
        ans[i]=-1e18;
        cin>>l[i]>>r[i];
        t[i]=lca(l[i],r[i]);
    }
    memset(fa,0,sizeof(fa));
    dfs2(rt);
    for(int i=1;i<=q;i++) ans[i]=max(calc(l[i],t[i])+w[t[i]],ans[i]);
    memset(fa,0,sizeof(fa));
    dfs3(rt);
    for(int i=1;i<=q;i++) ans[i]=max(calc(r[i],t[i])+w[t[i]],ans[i]);
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

Expected expr
原来你还活着

23小时前来自江西
0
- 亚洲卷王 AK IOI
  回复
  Expected expr
  ？？？
  
  23小时前来自北京
  0
- Expected expr
  回复
  亚洲卷王 AK IOI
  我还以为你退了
  
  23小时前来自江西
  0