专栏文章

题解：P11261 [COTS 2018] 直方图 Histogram

OOrinLoong
P11261题解参与者 5已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miq8n34f
此快照首次捕获于
2025/12/04 00:45
3 个月前
此快照最后确认于
2025/12/04 00:45
3 个月前
查看原文
更好的阅读体验？
码字不易，帮到你的话点个关注谢谢

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

Luogu Link

前言

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

题意简述

给定一宽为 nn 的直方图，第 ii 格的高度为 hih_i。也就是说，对于 ∀1≤i≤n\forall 1\le i\le n，第 ii 格矩形的四个顶点分别为 (i−1,0),(i,0),(i−1,hi),(i,hi)(i-1,0),(i,0),(i-1,h_i),(i,h_i)。
pEKIR3j.md.png
给定正整数 pp，求出满足以下条件的网格矩形的数量：
  • 有一条边在 xx 轴上。
  • 完全位于直方图内部。
  • 面积至少为 pp。

做法解析

首先想一想当一个矩形面积至少为 pp 时意味着什么——ab>pab>p。换句话说，当我们确定了矩形的高 bb 的时候，我们就随之确定了 a≥⌈pb⌉a\ge \lceil \frac{p}{b} \rceil。
我们发现，当矩形的 lx,rxlx,rx 确定之后，限制 ryry 范围的正是 min⁡i=lxrxhi\min_{i=lx}^{rx} h_i。此时套路来了：我们以 ii 为键，hih_i 为值建一棵小根笛卡尔树，并考虑横跨每个最小值的贡献。具体来说我们对这棵笛卡尔树做一遍 dfsdfs，每搜到一个结点 (i,hi)(i,h_i)，我们就统计所有 lc≤lx≤i,i≤rx≤rclc\le lx\le i,i\le rx\le rc 的合法矩形的数量，其中 lc,rclc,rc 分别为当前结点子树里横坐标的最小值和最大值。这么做的道理在于可以不重不漏地计数。
pEKIWgs.md.png
令当前结点 uu 的左子树大小为 LL，右子树大小为 RR（实际上，L=u−lc,R=rc−uL=u-lc,R=rc-u）。现在问题变成了计算所有结点的 ∑i=0L∑j=0Rmax⁡(hu−⌈pi+j+1⌉+1,0)\sum_{i=0}^L\sum_{j=0}^{R} \max(h_u-\lceil\frac{p}{i+j+1}\rceil+1,0)，其中的 ⌈pi+j+1⌉\lceil\frac{p}{i+j+1}\rceil 代表着 i,ji,j 确定后合法矩形高度的最小值，hu−⌈pi+j+1⌉+1h_u-\lceil\frac{p}{i+j+1}\rceil+1 则自然是 i,ji,j 确定后合法高度的种类。
pEKIfvn.md.png
考虑枚举较小的那一侧子树的 ii（这里是启发式合并思想，保证复杂度 O(Nlog⁡N)O(N\log N)）。不妨设 L<RL<R，问题变为如何快速计算 ∑i=0L∑k=i+1i+R+1max⁡(hu−⌈pk⌉+1,0)\sum_{i=0}^{L}\sum_{k=i+1}^{i+R+1}\max(h_u-\lceil\frac{p}{k}\rceil+1,0)。
显然最小的满足 hu−⌈pk⌉≥0h_u-\lceil\frac{p}{k}\rceil\ge 0 的 kk 就是 ⌈phu⌉\lceil\frac{p}{h_u}\rceil，
所以上式等价于算 ∑i=0L∑k=max⁡(i+1,⌈phu⌉)i+R+1hu−⌈pk⌉+1\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，
也即等价于 ∑i=0L(i+R+1−max⁡(i+1,⌈phu⌉))×hu−∑k=max⁡(i+1,⌈phu⌉)i+R+1⌈pi⌉\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。
注意到我们减去的那玩意就是个 ⌈pi⌉\lceil \frac{p}{i} \rceil 的前缀和，预处理之即可。这道题就做完了！
时间复杂度 O(Nlog⁡N)O(N\log N)。

代码实现

代码很简单!
CPP
#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;
}

反思总结

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

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...