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

· · 题解

what can I say.

三篇题解撤了两篇，怎么说？

但看在没有简单暴力的二阶差分做法下，还是写一篇罢。不懂二阶差分的可以左转 bdfs。

思路

发现 h_i\le10^9，很大，但由于只有 n 个高，所以难免重复的答案。考虑一个常见套路，对于一个高度 h_i，找到最大的 l 满足 l<i 且 h_l<h_i 和最小的 r 满足 i<r 且 h_i>h_r，那么底边在区间 (l,r) 内，高度在 (\max(h_l,h_r),h_i] 之间的矩形是可能可以快速计算个数的，因为满足合法，且高度有单调性。并且全都按此方案计算的话是不会算重的，因为在 (l,r) 区间中，h_j>h_i 的显然有 \max(h_{l'},h_{r'})\ge h_i，不会算重；而 h_j=h_i 的直接不算；h_j<h_i 的最近也是 h_l 和 h_r 了，而高度 H>\max(h_l,h_r) 的矩形显然也不会影响它们。给出这部分代码：

scanf("%d%lld",&n,&p);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    m=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+m,a[i])-b;
        while(top&&a[stk[top]]>=a[i])top--;//h[l]<h[i]
        L[i]=stk[top];
        stk[++top]=i;
    }
    stk[top=0]=n+1;
    for(int i=n;i;i--){
        while(top&&a[stk[top]]>a[i])top--;//h[r]<=h[i]
        R[i]=stk[top];
        stk[++top]=i;
        if(a[R[i]]!=a[i]){//当h[r]=h[i]直接不算
            /*计算答案*/
        }
    }

那么知道 (l,r) 了也知道高度范围了，那该怎么算答案呢？我们都知道，一个底边为 len 的矩形，如果面积想要至少为 p 那么 h\ge\lceil \frac{p}{len} \rceil，对于每一个底边为 len 的且 \max(h_l,h_r)<h\le h_i 的，答案是 (h_i-h+1)\times(r-l+1-len+1)，拆一下柿子是 h_i\times(r-l+1-len+1)-(h-1)\times(r-l+1-len+1)，显然是可以分别维护的。在求取 \min len 满足至少高度 \lceil \frac{p}{\min len} \rceil\le h_i，\max len 满足至少高度 \lceil \frac{p}{\max len} \rceil>\max(h_l,h_r) 的情况下，\min len 到 \max len 中的 r-l+1-len+1 这一贡献形成了等差数列，直接二阶差分跑路。而 \lceil \frac{p}{len} \rceil\le\max(h_l,h_r) 这一部分的答案是 (h_i-\max(h_l,h_r))\times (r-l+1-len+1)，也可以二阶差分维护。给出代码，其中差分数组我开了两个，分别存值和个数。

if(a[R[i]]!=a[i]){
            int len=R[i]-1-L[i];
            long long l=max(1ll,p/b[a[i]]+(p%b[a[i]]!=0)),r=(!max(b[a[L[i]]],b[a[R[i]]])?len:min(1ll*len,p/max(b[a[L[i]]],b[a[R[i]]])-(p%max(b[a[L[i]]],b[a[R[i]]])==0)));
            if(l<=r){
                c[l]+=(__int128)(len-l+1)*b[a[i]];
                c[l+1]+=(__int128)(-1-(len-l+1))*b[a[i]];
                c[r+1]+=(__int128)(1-(len-r+1))*b[a[i]];
                c[r+2]+=(__int128)(len-r+1)*b[a[i]];
                d[l]+=len-l+1;
                d[l+1]+=-1-(len-l+1);
                d[r+1]+=1-(len-r+1);
                d[r+2]+=len-r+1;
            }
            if(++r<=len){
                int x=b[a[i]]-max(b[a[L[i]]],b[a[R[i]]]);
                c[r]+=(__int128)(len-r+1)*x;
                c[r+1]+=(__int128)(-1-(len-r+1))*x;
                c[len+2]+=x;
            }
        }

然后就没了，注意可能会爆 long long。附上结尾部分的代码：

    for(int i=1;i<=n;i++){
        c[i]+=c[i-1];
        d[i]+=d[i-1];
    }
    for(int i=1;i<=n;i++){
        c[i]+=c[i-1];
        d[i]+=d[i-1];
        long long h=p/i+(p%i!=0);
        ans+=c[i]-d[i]*(h-1);
    }
    print(ans);