自动搬运

查看原文

来自洛谷，原作者为

	OrinLoong 刷题有条不紊，功力日日渐深

搬运于2025-08-24 23:05:49，当前版本为作者最后更新于2025-02-16 17:33:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验？

码字不易，帮到你的话点个关注谢谢

LGP11261 [COTS 2018] 直方图 学习笔记

Luogu Link

前言

参考了这篇题解。算是对其更详细的一个解释。

题意简述

给定一宽为 $n$ 的直方图，第 $i$ 格的高度为 $h_i$。也就是说，对于 $\forall 1\le i\le n$，第 $i$ 格矩形的四个顶点分别为 $(i-1,0),(i,0),(i-1,h_i),(i,h_i)$。

给定正整数 $p$，求出满足以下条件的网格矩形的数量：

• 有一条边在 $x$ 轴上。
• 完全位于直方图内部。
• 面积至少为 $p$。

做法解析

首先想一想当一个矩形面积至少为 $p$ 时意味着什么——$ab>p$。换句话说，当我们确定了矩形的高 $b$ 的时候，我们就随之确定了 $a\ge \lceil \frac{p}{b} \rceil$。

我们发现，当矩形的 $lx,rx$ 确定之后，限制 $ry$ 范围的正是 $\min_{i=lx}^{rx} h_i$。此时套路来了：我们以 $i$ 为键，$h_i$ 为值建一棵小根笛卡尔树，并考虑横跨每个最小值的贡献。具体来说我们对这棵笛卡尔树做一遍 $dfs$，每搜到一个结点 $(i,h_i)$，我们就统计所有 $lc\le lx\le i,i\le rx\le rc$ 的合法矩形的数量，其中 $lc,rc$ 分别为当前结点子树里横坐标的最小值和最大值。这么做的道理在于可以不重不漏地计数。

令当前结点 $u$ 的左子树大小为 $L$，右子树大小为 $R$（实际上，$L=u-lc,R=rc-u$）。现在问题变成了计算所有结点的 $\sum_{i=0}^L\sum_{j=0}^{R} \max(h_u-\lceil\frac{p}{i+j+1}\rceil+1,0)$，其中的 $\lceil\frac{p}{i+j+1}\rceil$ 代表着 $i,j$ 确定后合法矩形高度的最小值，$h_u-\lceil\frac{p}{i+j+1}\rceil+1$ 则自然是 $i,j$ 确定后合法高度的种类。

考虑枚举较小的那一侧子树的 $i$（这里是启发式合并思想，保证复杂度 $O(N\log N)$）。不妨设 $L<R$，问题变为如何快速计算 $\sum_{i=0}^{L}\sum_{k=i+1}^{i+R+1}\max(h_u-\lceil\frac{p}{k}\rceil+1,0)$。
显然最小的满足 $h_u-\lceil\frac{p}{k}\rceil\ge 0$ 的 $k$ 就是 $\lceil\frac{p}{h_u}\rceil$，
所以上式等价于算 $\sum_{i=0}^{L}\sum_{k=\max(i+1,\lceil\frac{p}{h_u}\rceil)}^{i+R+1} h_u-\lceil\frac{p}{k}\rceil+1$，
也即等价于 $\sum_{i=0}^L (i+R+1-\max(i+1,\lceil\frac{p}{h_u}\rceil))\times h_u-\sum_{k=\max(i+1,\lceil\frac{p}{h_u}\rceil)}^{i+R+1} \lceil \frac{p}{i} \rceil$。
注意到我们减去的那玩意就是个 $\lceil \frac{p}{i} \rceil$ 的前缀和，预处理之即可。这道题就做完了！

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

代码实现

代码很简单!

#include <bits/stdc++.h>
using namespace std;
namespace obasic{
    typedef long long lolo;
    template <typename _T>
    void readi(_T &x){
        _T k=1;x=0;char ch=getchar();
        for(;!isdigit(ch);ch=getchar())if(ch=='-')k=-1;
        for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
        x*=k;return;
    }
    template <typename _T>
    void writi(_T x){
        if(x<0)putchar('-'),x=-x;
        if(x>9)writi(x/10);
        putchar(x%10+'0');
    }
    template <typename _T>
    void maxxer(_T &x,_T y){x=max(x,y);}
    template <typename _T>
    _T pcedi(_T x,_T y){return (x-1)/y+1;}
};
using namespace obasic;
const int MaxN=1e5+5;
int N,H[MaxN],stk[MaxN],ktp;
int ls[MaxN],rs[MaxN];lolo P,pre[MaxN],ans;
lolo calc(lolo l,lolo r,lolo h){
    maxxer(l,pcedi(P,h));if(l>r)return 0;
    return 1ll*(h+1)*(r-l+1)-(pre[r]-pre[l-1]);
}
lolo solve(int u,int cl,int cr){
    lolo res=0;int lsiz=u-cl,rsiz=cr-u;
    if(lsiz>rsiz)swap(lsiz,rsiz);
    lsiz++;for(int i=1;i<=lsiz;i++)res+=calc(i,i+rsiz,H[u]);
    if(ls[u])res+=solve(ls[u],cl,u-1);
    if(rs[u])res+=solve(rs[u],u+1,cr);
    return res;
}
signed main(){
    readi(N),readi(P);
    for(int i=1;i<=N;i++)pre[i]=pre[i-1]+pcedi(P,(lolo)i);
    for(int i=1;i<=N;i++)readi(H[i]);
    for(int i=1;i<=N;i++){
        int k=ktp;
        while(k&&H[stk[k]]>H[i])k--;
        if(k)rs[stk[k]]=i;
        if(k<ktp)ls[i]=stk[k+1];
        stk[++k]=i,ktp=k;
    }
    ans=solve(stk[1],1,N);writi(ans);
    return 0;
}

反思总结

我们考虑有顺序地枚举限制矩形高度的 $h_i$，于是把问题搬到了笛卡尔树上！大概是一种套路。
更深刻的东西暂时想不出来/ll