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

· · 题解

更好的阅读体验？

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

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，求出满足以下条件的网格矩形的数量：

做法解析

首先想一想当一个矩形面积至少为 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