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

_Ch1F4N_ · 2024-11-08 18:59:27 · 题解

考虑到确定了 x 轴上的范围后，限制 y 轴范围的是区间中 h 的最小值，于是对原序列建立出小根笛卡尔树，我们考虑横跨每个最小值的贡献。

假设当前点左子树大小为 L 右子树大小为 R，其贡献就是 \sum_{i=0}^L \sum_{j=0}^R \max(h - \left\lceil\dfrac{p}{i+j+1}\right\rceil + 1,0)。

考虑枚举 L,R 中较小的那个也就是去做启发式合并，我们需要快速计算 \sum_{i=l}^r \max(h - \left\lceil\dfrac{p}{i}\right\rceil,0)。

根据数论知识注意到满足 h - \left\lceil\dfrac{p}{i}\right\rceil \geq 0 的最小 i 刚好是 \left\lceil\dfrac{p}{h}\right\rceil，于是外面的 \max 就被我们拆掉了，我们要处理的只剩下 \left\lceil\dfrac{p}{i}\right\rceil 的前缀和，O(n) 预处理下即可。

总时间复杂度 O(n \log n)，常数小并且非常好写。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5+114;
int stk[maxn],tp;
int n,h[maxn],p;
int ls[maxn],rs[maxn];
int pre[maxn];
int calc(int l,int r,int c){
    c++;
    l=max(l,(p+c-1)/c);
    if(l<=r) return c*(r-l+1)-pre[r]+pre[l-1];
    else return 0;
}
int ans;
void solve(int cur,int l,int r){
    if(cur==0) return ;
    solve(ls[cur],l,cur-1);
    solve(rs[cur],cur+1,r);
    int L=cur-l+1,R=r-cur+1;
    if(L>R) swap(L,R);
    for(int i=1;i<=L;i++) ans+=calc(i,i+R-1,h[cur]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+(p+i-1)/i;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        int k=tp;
        while(k>0&&h[stk[k]]>h[i]) k--;
        if(k!=0) rs[stk[k]]=i;
        if(k<tp) ls[i]=stk[k+1];
        tp=k;
        stk[++tp]=i;
    }
    solve(stk[1],1,n);
    cout<<ans<<'\n';
    return 0;
}