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

· · 题解

来一发线性做法。

首先考虑枚举区间如何计算这个区间的答案，可以发现对于区间 [l,r] 至少需要建立一个高度为 \left\lceil\frac{p}{r-l+1}\right\rceil 的矩形，而矩形高度又受到区间 h 最小值限制，不能超过这个值。所以答案实际上就是：

\sum\limits_{l=1}^{n}\sum\limits_{r=l}^n \max(\min\limits_{i=l}^r h_i-\left\lceil\frac{p}{r-l+1}\right\rceil+1,0)

考虑枚举 r 或者其他东西没有什么好的做法，容易想到枚举 \min\limits_{i=l}^r h_i，考虑每个位置做第一个最小值的区间产生的贡献。

考虑每个位置 i 前面第一个小于等于自己的数的位置 l_i（没有设置为 0）和后面第一个小于自己的数的位置 r_i（没有设置为 n+1），则它做第一个最小值的区间为 (l_i,r_i)，其中左端点在 (l_i,i] 之间，右端点在 [i,r_i) 之间。

我们现在确定了 \min 的值，不妨记为 v，为了让我们答案中的 \max 有效（不为 0），我们需要让区间长度大于等于 lim=\left\lceil\frac{p}{v}\right\rceil。

考虑怎么统计所有长度大于等于 lim 的区间产生的 v-\left\lceil\frac{p}{len}\right\rceil+1 的和。可以发现事实上只有三类区间。

下面不妨记左端点可取值有 L 个（L=i-l_i），右端点可取值有 R 个（R=r_i-i）。

注意上方对区间计算和式时下界需要和 lim 取 \max。

运算过程中可能会爆 long long，但答案不会爆。所以 unsigned long long 自然溢出即可。

时间复杂度为 \mathcal O(n)。

代码里面我写成了笛卡尔树。实际上是不用的。

int n;
ll p;
int h[N];
int minn[N][17],idx[N][17];
int tot;
int ls[N],rs[N];
int L[N],R[N];
ull val[N];
int cut[N];
int rt;
pii merge(pii x,pii y){
    if(x.fi==y.fi) return mp(x.fi,min(x.se,y.se));
    return min(x,y);
}
pii query(int l,int r){
    int len=__lg(r-l+1);
    return merge(mp(minn[l][len],idx[l][len]),mp(minn[r-(1<<len)+1][len],idx[r-(1<<len)+1][len]));
}
void build(int &x,int l,int r){
    tot++,x=tot;
    L[tot]=l,R[tot]=r;
    if(l>r) return void();
    tie(val[x],cut[x])=query(l,r);
    build(ls[x],l,cut[x]-1);
    build(rs[x],cut[x]+1,r);
}
ull pres[N];
ull press[N];
ull ans;
ull sum(int l,int r){
    return 1ull*(l+r)*(r-l+1)/2;
}
void calc(int x){
    if(L[x]>R[x]) return;
    ull lim=(p+val[x]-1)/val[x];
    int lef=cut[x]-L[x]+1;
    int rig=R[x]-cut[x]+1;
    {
        ull le=max(lim,1ull),re=min(lef,rig);
        if(le<=re){
            ans-=pres[re]-pres[le-1];
            ans+=sum(le,re)*(val[x]+1);
        }
    }
    {
        ull le=max(lim,min(lef,rig)+1ull),re=max(lef,rig);
        if(le<=re){
            ull coef=min(lef,rig);
            ans-=coef*(press[re]-press[le-1]);
            ans+=coef*(re-le+1)*(val[x]+1);
        }
    }
    {
        ull le=max(lim,max(lef,rig)+1ull),re=R[x]-L[x]+1;
        if(le<=re){
            ans-=(re+1)*(press[re]-press[le-1]);
            ans-=sum(le,re)*(val[x]+1);
            ans+=(re+1)*(re-le+1)*(val[x]+1);
            ans+=pres[re]-pres[le-1];
        }
    }
    calc(ls[x]);
    calc(rs[x]);
}
// #define Shun cute
int main(){
#ifdef Shun
    freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n>>p;
    fr1(i,1,n) pres[i]=pres[i-1]+1ull*i*((p+i-1)/i);
    fr1(i,1,n) press[i]=press[i-1]+1ull*(p+i-1)/i;
    fr1(i,1,n) cin>>h[i];
    fr1(i,1,n) minn[i][0]=h[i],idx[i][0]=i;
    fr1(j,1,16){
        fr1(i,1,n-(1<<j-1)){
            tie(minn[i][j],idx[i][j])=merge(mp(minn[i][j-1],idx[i][j-1]),mp(minn[i+(1<<j-1)][j-1],idx[i+(1<<j-1)][j-1]));
        }
    }
    build(rt,1,n);
    calc(rt);
    cout<<ans<<'\n';
    ET;
}