浅谈最值分治——解决有关区间最值类计数问题的利器

Magus · 2026-07-30 17:35:59 · 算法·理论

介绍

最值分治是一种基于笛卡尔树的思想的特殊的分治方法。它不按照区间的中点分治，而是按照区间的最值进行分治，这种特殊的分治方法在处理起与区间最值相关的计数之类的问题时非常的轻松好用。

做法

最值分治利用了笛卡尔树的一个性质：设一个区间 [l,r] 最值的位置为 p，可以把区间分成 [l,p] 和 [p,r] 两个区间，这两个区间互不影响。也就是说左边怎么填数跟右边一点关系也没有。当然，有一些题目也会出现左右区间有关的情况，这个时候我们就要枚举一个子区间，与另一个子区间进行答案的统计了，统计方法详见下文。

最值分治一般的步骤如下：设 f(l,r) 表示区间 [l,r] 的答案，然后从小的区间往大的区间合并统计答案。如：

f(l,r)=f(l,p-1) \times f(p+1,r)

其中 p 是区间 [l,r] 的最值的位置。

所以我们只需要在每次分治时知道每个区间的最值即可，但是直接扫一遍区间是不行的，复杂度最坏情况会退化到 \mathcal{O}(n^2)。如果有确定的数列，使用 ST 表即可 \mathcal{O}(1)。如果需要遍历区间来找，我们一般使用类似于双指针的方法来找到这个最值：

l \to r \to l+1 \to r-1 \to \dots

这个东西均摊下来复杂度是 \mathcal{O}(\log n) 的，可以感性理解一下，相当于把 n 次遍历变成了 2\min(i,n-i) 次，且其遍历次数最多时恰好是最小值在中间的情况，也就是近似 \log。~~真的不是我不会严谨证明~~

还有一种情况便是对于一个区间，需要枚举一个子区间（分治完的左区间或右区间）来与另一个区间一起统计答案，也就是上文提到的情况。这种情况我们一般使用启发式分治的思想，也就是枚举区间长度较小的那个子区间，这样每个点最多会被枚举 \mathcal{O}(\log n) 次。

例题

CF2234E

板子题。

::::info[如何联系？] 观察性质，手玩几组样例，能否与上文写的内容建立起联系，如何联系到最值？ ::::

::::success[题解] 观察这个数组 a 有什么性质，手玩几组样例：

1 4 1：此时 p_2 作为最小值覆盖的区间为 4，容易发现它一定是 p 整个序列中的最小值。
1 6 1 2 此时 p_2 作为最小值覆盖的区间为 6，容易发现它一定是 p 整个序列中的最小值。
3 3 3 此时 \sum a_i 为 9，而长度为 3 的序列的区间总数为 \frac{3(3+1)}{2}=10，此时一定无解。

所以我们就得到了本题的一些基本性质：

当 \sum a_i \neq \frac{n(n+1)}{2} 时无解。
当 a_i=i(n-i+1) 时，p_i 为 p 整个序列中的最小值。这个很好证明，因为当 p_i 为 p 整个序列中的最小值时，包含它的所有区间的最小值一定都是它，而区间总数即前面选 i 个起点，后面选 n-i+1 个终点，即 i(n-i+1)。并且，这个结论可以推广到任意一个区间 [l,r]，当 a_q=(q-l+1)(r-q+1) 时，它是 [l,r] 的最小值。

那我们知道了这个最小值 p_i 之后就好办了。我们发现这个最小值左边和右边的答案相互是独立的，因为如果有一段区间横跨中间，那么这个区间的最小值一定为 p_i，这个结论可以推广到任何一个区间，于是我们便能进行最值分治了。

::::

::::info[合并的式子是什么？]

直接套上上文说的 f(l,r) 表示区间的答案，思考：填这些数的方案数是多少？我们关心它们的具体值吗？

::::

::::success[题解]

具体地，我们设 f(l,r) 表示区间 [l,r] 的答案，q 为 [l,r] 内最小值的位置，易得：

f(l,r)=f(l,q-1) \times f(q+1,r) \times \text{C}^{q-l}_{r-l}

这个 \text{C}^{q-l}_{r-l} 是如何得到的呢？因为最小值的位置已经确定，所以此时 [l,r] 内待定的数共有 r-l+1-1=r-l 个，而我们只关心这些数的相对关系（因为 a_i 只确定了相对关系），并且 p 为一个排列，每个 p_i 互不相同，所以我们可以随便填数，因为区间内的相对大小已经确定，所以选完左边的右边的也确定了，即 q-l。

::::

::::info[无解的情况？]

我们把式子写出来了，有解的情况已经做完了，那无解的情况都有哪些呢？请确保你思考完全。

::::

::::success[题解]

紧接着我们来考虑无解的情况，显然地，当 [l,r] 内没有 i 使得 a_i=(i-l+1)(r-i+1) 时无解，当 [l,r] 内出现了一个 i 且 a_i>(i-l+1)(r-i+1) 时无解。

以及，当 [l,r] 中出现了多个合法的 a_i 时无解，在判这个的时候我们可以任取一个合法的 a_i 直接进行分治，为什么呢？因为分治的区间肯定是越来越短的，如果存在另外一个合法的 a_i，那么他肯定会在之后的分治中被查到，那么便会触发条件 a_i>(i-l+1)(r-i+1)，殊途同归了。

::::

::::success[区间找最值]

那么我们就剩下了最后一个问题：如何快速地找到这个最小值呢？请注意：最值分治并没有保证分治出的两个区间长度相等，也就是说，会有可能出现最小值永远偏向一边的情况，如果你遍历区间 [l,r] 来找的话，你会被卡到 \Theta(n^2)。

上文写的方法这里就能用到了。我们使用一个双指针来搜：

l \to r \to l+1 \to r-1 \to \dots

所以我们就做完了这个题，代码非常好写虽然我写的很难看。

::::

::::success[Code]

//风が私を呼んでいる
#include<bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) 
#define int long long
#define I using
#define AK namespace
#define CSPS2026 std
I AK CSPS2026;
const int maxn=1e6+10,maxm=1e3+10,mod=1e9+7;
int t,n,m,x,y,z,u,v,w,arr[maxn],fac[maxn],inv[maxn];
int kasumi(int x,int y,int p)
{
    int res=x,ans=1;
    while(y)
    {
        if(y&1)
        {
            ans*=res;
            ans%=p;
        }
        res*=res;
        res%=p;
        y>>=1;
    }
    return ans;
}
void init()
{
    fac[0]=1;
    for(int i=1;i<=1000000;i++)fac[i]=fac[i-1]*i%mod;
    inv[1000000]=kasumi(fac[1000000],mod-2,mod);
    for(int i=999999;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int split(int l,int r)
{
    if(l>=r)return 1;
    int i=l,j=r,res=0;
    for(int tot=l;tot<=r;tot++)
    {
        if(tot&1)
        {
            if(arr[i]>(i-l+1)*(r-i+1))return 0;
            if(arr[i]==(i-l+1)*(r-i+1))
            {
                if(!res)res=1;
                res*=split(l,i-1);
                res%=mod;
                res*=split(i+1,r);
                res%=mod;
                res*=C(r-l,i-l);
                res%=mod;
                break;
            }
            i++;
        }
        else
        {
            if(arr[j]>(j-l+1)*(r-j+1))return 0;
            if(arr[j]==(j-l+1)*(r-j+1))
            {
                if(!res)res=1;
                res*=split(l,j-1);
                res%=mod;
                res*=split(j+1,r);
                res%=mod;
                res*=C(r-l,j-l);
                res%=mod;
                break;
            }
            j--;
        }
    }
    return res; 
} 
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout); 
    FastIO;
    cin>>t;
    init();
    while(t--)
    {
        u=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>arr[i];
            u+=arr[i];
        }
        if(u!=((n*(n+1))>>1))
        {
            cout<<"0\n";
            continue;
        }
        int ans=split(1,n);
        cout<<ans<<"\n";    
    }
    return 0;
}
/*
出好的题！
覆知盖点广识，题着切有目实合的际景背，解较比然自法。
出给题赞点人！
更的要据重是数正本基确，符一合好道的本题标准基！
*/

::::

P16902

与上一题长得十分相似，读者可以自行练习。

这是题解

CF1913D

::::info[思考]

还是先进行分析，观察它与最值分治的联系。

::::

::::success[题解]

首先删到不能再删的情况为：只剩下一个全局最小值。

对于 [l,r]，不难想到有 f(l,r)=f(l,u-1)\times f(u+1,r)，其中 u 还是区间最小值的位置，为了防止歧义改了一下名字，然后分类讨论：

当 l>r 时只有空集（全删完）的情况，答案为 1。
当 l=r 时，若 a_l 是全局最小值，那么它必须留下，不能被删除，答案为 1。否则有删或者不删两种情况，答案为 2。

求最小值的位置用 ST 表。

::::

::::warning[结果的问题]

尝试自己写一遍，你会发现答案小了，手模一遍试试看！

::::

::::success[题解]

手模一遍这个过程，我们发现有些情况没被统计，例如：

2,4,1,3

分治：

[2,4],1,[3]

f(1,4)=f(1,2)\times f(4,4)

其中 f(4,4) 答案为 2。

f(1,2)=f(1,0) \times f(2,2)

其中 f(1,0) 答案为 1，f(2,2) 答案为 2，最终的答案就是 4，但正确的答案为 6。我们发现 2 被删除的情况是没有统计进答案里的。这种情况如何处理呢？其实很简单，对于 [l,r] 这个区间，内部是不可能再产生贡献的，所以考虑外部元素对它的影响。

同理，要是右边有，那它也能被右边的删光，加上 f(1,u-1)。
要是都有，需要去除全部空集的情况。
要是都没有，说明 p_u 为全局最小值，不用动。

问题转变为求区间最小值，ST 表可以轻松解决。

::::

::::success[Code]

//-static -std=c++14 -O2 -Wall -Wl,--stack=2147483647 -Wshadow
//风が私を呼んでいる
#include<bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define I using
#define AK namespace
#define CSPS2026 std
I AK CSPS2026;
const int maxn=3e5+10,maxm=1e3+10,mod=998244353,inf=1e18;
int t,n,m,x,y,z,u,v,w,mn,arr[maxn];
struct node
{
    int id,val;
}st[maxn][25];
void init()
{
    for(int i=1;i<=20;i++)
    {
        int j=n-(1<<i)+1;
        for(int k=1;k<=j;k++)
        {
            if(st[k][i-1].val<st[k+(1<<(i-1))][i-1].val)st[k][i]=st[k][i-1];
            else st[k][i]=st[k+(1<<(i-1))][i-1];
        }
    }
    return;
}
int query(int l,int r)
{
    int k=__lg(r-l+1);
    if(st[l][k].val<st[r-(1<<k)+1][k].val)return st[l][k].id;
    else return st[r-(1<<k)+1][k].id;
}
int split(int l,int r)
{
    if(l>r)return 1;
    if(l==r and arr[l]==mn)return 1;
    else if(l==r)return 2;
    int res=0,pos=query(l,r);
    res+=split(l,pos-1)*split(pos+1,r);
    int flag=0;
    if(r<n and arr[query(r+1,n)]<=arr[pos])res+=split(l,pos-1),flag++;
    res%=mod;
    if(l>1 and arr[query(1,l-1)]<=arr[pos])res+=split(pos+1,r),flag++;
    if(flag==2)res--;
    res+=mod;
    res%=mod;
    return res;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    FastIO;
    cin>>t;
    while(t--)
    {
        mn=1e18;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>arr[i],st[i][0].val=arr[i],st[i][0].id=i,mn=min(mn,arr[i]);
        init();
        int ans=split(1,n);
        cout<<ans%mod<<"\n";
    }
    return 0;
}
/*
出好的题！
覆知盖点广识，题着切有目实合的际景背，解较比然自法。
出给题赞点人！
更的要据重是数正本基确，符一合好道的本题标准基！
*/

::::

P4755

::::info[思考]

乍一看似乎和最值之类的没有任何关系，但真的是这样吗？显然这道题便是会跨越左右区间的一个典例。想一想上文的实现方法。

::::

::::success[题解]

还是设 p 为区间 [i,j] 中最大值的位置。左右区间单独的可以轻松求出来，那跨越 p 这个位置的区间呢？

我们发现，跨越 p 这个位置的区间的最大值肯定为 a_p。那么有：

a_i\times a_j \leq \max\limits_{k=i}^j a_k

a_i\times a_j \leq a_p

\frac{a_p}{a_i} \geq a_j

我们采用启发式合并的思想，枚举长度小的那个区间，问题转变为求对于每个 a_i 在 [p,j] 区间内有多少个 a_j 满足上面这个式子的个数。数据范围可以让你随便用啥数据结构都行，我这里用的是分块。 ::::

::::success[Code]

//风が私を呼んでいる
#include<bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) 
#define int long long
#define I using
#define AK namespace
#define CSPS2026 std
I AK CSPS2026;
const int maxn=2e5+10,maxm=1e3+10,mod=998244353;
int t,n,m,x,y,z,u,v,w,len,ans,arr[maxn],id[maxn],sum[maxn];
vector<int>blk[maxn];
struct st
{
    int id,val;
}st[maxn][25];
void build(int k)
{
    blk[k].clear();
    int l=(k-1)*len+1,r=min(k*len,n);
    for(int i=l;i<=r;i++)blk[k].push_back(arr[i]);
    sort(blk[k].begin(),blk[k].end());
    return;
}
void update(int l,int r,int x)
{
    int idx=id[l],idy=id[r];
    for(int i=l;i<=min(r,idx*len);i++)arr[i]+=x;
    build(idx);
    if(idx+1<=idy-1)for(int i=idx+1;i<=idy-1;i++)sum[i]+=x;
    if(idx!=idy)
    {
        for(int i=(idy-1)*len+1;i<=r;i++)arr[i]+=x;
        build(idy);
    }
    return;
}
int querymx(int l,int r,int val)
{
    int res=0,idx=id[l],idy=id[r];
    for(int i=l;i<=min(r,idx*len);i++)if(arr[i]+sum[idx]<=val)res++;
    if(idx+1<=idy-1)
    {
        for(int i=idx+1;i<=idy-1;i++)
        {
            int tar=val-sum[i];
            res+=upper_bound(blk[i].begin(),blk[i].end(),tar)-blk[i].begin();
        }
    }
    if(idx!=idy)for(int i=(idy-1)*len+1;i<=r;i++)if(arr[i]+sum[idy]<=val)res++;
    return res;
}
void init()
{
    for(int i=1;i<=20;i++)
    {
        int j=n-(1<<i)+1;
        for(int k=1;k<=j;k++)
        {
            if(st[k][i-1].val>st[k+(1<<(i-1))][i-1].val)st[k][i]=st[k][i-1];
            else st[k][i]=st[k+(1<<(i-1))][i-1];
        }
    }
    return;
}
int query(int l,int r)
{
    int k=__lg(r-l+1);
    if(st[l][k].val>st[r-(1<<k)+1][k].val)return st[l][k].id;
    else return st[r-(1<<k)+1][k].id;
}
int split(int l,int r)
{
    int res=0;
    if(l>r)return 0;
    if(l==r)
    {
        res+=(arr[l]*arr[l]<=arr[l]);
        return res;
    }
    int cur=query(l,r);
    res+=split(l,cur-1);
    res+=split(cur+1,r);
    if(cur-l+1<r-cur+1)for(int i=l;i<=cur;i++)res+=querymx(cur,r,arr[cur]/arr[i]);
    else for(int i=cur;i<=r;i++)res+=querymx(l,cur,arr[cur]/arr[i]);
    return res;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout); 
    FastIO;
    cin>>n;
    len=sqrt(n); 
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        st[i][0].val=arr[i];
        st[i][0].id=i;
        id[i]=(i-1)/len+1;
    }
    for(int i=1;i<=id[n];i++)build(i);
    init();
    ans=split(1,n);
    cout<<ans;
    return 0;
}
/*
出好的题！
覆知盖点广识，题着切有目实合的际景背，解较比然自法。
出给题赞点人！
更的要据重是数正本基确，符一合好道的本题标准基！
*/

::::

写在最后

最值分治让我们看到，当一个问题中的元素之间存在"最值关系"时，我们可以利用这个关系来划分问题空间。这种"利用问题结构来分治"的思路，能让你非常轻松易懂的解决一些难题。

希望这篇文章能帮你打开一扇新的大门，让你在相关问题时，能多一个思考的方向。

习题

CF875D

P9607

P12624