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

ingo_dtw · 2026-05-23 10:52:42 · 题解

这么经典的题必须来篇题解。

看到这种矩形统计方案数的题目我们不难想到建立一颗小根堆笛卡尔树。

现在对于这个节点 u 我们不难想到需要枚举对于这个节点为根的子树内包含的节点是个 [l_u,r_u] 的连续区间。

所以我们考虑对于这个笛卡尔树做分治，在 u 节点我们只处理跨过 u 这个节点的矩形，其他的交给它的左右子节点来处理，那么我们现在考虑枚举这个矩形的左边界与右边界即 L\in[l_u,u],R \in [u,r_u]，所以对于 u 节点的答案为：

但是这样时间复杂度显然是 \mathcal{O}(n^2) 的，所以我们考虑启发式合并。

那么我们只有 w=R-L+1 这个东西不是个定值，那么我们考虑只枚举较小的一侧，假设我们枚举 L 那么：

不难注意到这其实是一段连续的区间是可以考虑 \mathcal{O}(1) 算的，而我们需要求：\sum \max\{0,h_u-\lceil\frac{p}{w}\rceil+1\}

但是这个 \max 很烦，但是你发现对于 h_u<\lceil \frac{p}{w} \rceil 没有贡献，所以我们现在考虑只统计 h_u\ge \lceil \frac{p}{w} \rceil 所以我们的 w 不妨从 \lceil \frac{p}{h_u}\rceil 开始枚举，所以式子变为：

拆一下式子（设 A=\max\{\lceil \frac{p}{h_u}\rceil,u-L+1\},B=r_u-L+1）：

你不难注意到这个最后的求和式子是可以前缀和算的，然后只枚举 R 也是同理，于是我们就做完了，时间复杂度 \mathcal{O}(n \log n)。

:::success[Ac Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long 
#define ull unsigned long long
// #define R register
#define rint register int
#define _ read<int>()
inline bool blank(const char &x)
{
    return !(x^13)||!(x^32)||!(x^10)||!(x^9);
}
template<class T>inline T read()
{
    T r=0,f=1;char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();!blank(x)&&(x^-1);x=gc());
}

const int N=1e5+10;
struct Node
{
    int ls,rs,x;
}tr[N];
int n,p,sta[N],top,rt,s[N],ans;
inline void dfs(rint u,rint l,rint r)
{
    if(!u) return;
    // cerr<<u<<' '<<l<<' '<<r<<endl;
    dfs(tr[u].ls,l,u-1);
    dfs(tr[u].rs,u+1,r);
    if(u-l<=r-u)
    {
        for(rint L=l;L<=u;++L)
        {
            rint A=max((p+tr[u].x-1)/tr[u].x,u-L+1),B=r-L+1;
            if(A<=B) ans+=(tr[u].x+1)*(B-A+1)-(s[B]-s[A-1]);
        }
    }
    else
    {
        for(rint R=u;R<=r;++R)
        {
            rint A=max((p+tr[u].x-1)/tr[u].x,R-u+1),B=R-l+1;
            if(A<=B) ans+=(tr[u].x+1)*(B-A+1)-(s[B]-s[A-1]);
        }
    }
}
signed main() 
{  
    n=_,p=_;
    for(rint i=1;i<=n;++i) tr[i]={0,0,_};
    for(rint i=1;i<=n;++i)
    {
        while(top&&tr[sta[top]].x>tr[i].x) --top;
        if(top) tr[i].ls=tr[sta[top]].rs,tr[sta[top]].rs=i;
        else tr[i].ls=sta[top+1],rt=i;
        sta[++top]=i;
    }
    for(rint i=1;i<=n;++i) s[i]=s[i-1]+(p+i-1)/i;
    dfs(rt,1,n);
    out(ans);
    return 0; 
} 
//我也要写吗

:::