贪心、线段树

又是赛时没做出来的题，思路是线段树维护序列，从右到左遍历，如果 $a_i$ 能够通过操作让右边的一部分元素的平均值变大，就把 $a_i$ 的值平摊到区间 $[i,r]$（其中 $r$ 是 $a_i$ 能够贡献到的最远右边界，通过二分求出），将 $[i,r]$ 的前一部分元素赋值为 $\left\lfloor \dfrac{sum_{i,r}}{(r-i+1)} \right\rfloor$，其余元素赋值为 $\left\lceil \dfrac{sum_{i,r}}{(r-i+1)} \right\rceil$。最后遍历序列取最小值和最大值计算答案。

错误之处在于二分的时候只比较了 $a_i$ 和区间 $[i+1,mid]$ 平均值 $\dfrac{sum_{i+1,mid}}{(mid-i)}$ 的大小，如果弄一个区间 $[i+1,mid]$ 并且让 $[i+1,mid-1]$ 是很小的数而 $a_{mid}$ 是一个大数时判断条件成立导致 $a_{mid}$ 会被顺带摊平变小，例如 $[3,2,4]$ 会被摊成 $[3,3,3]$，$[10,1,2,8]$ 会被摊成 $[5,5,5,6]$。

必有其败因。

改正上面的做法，二分时对当前区间进行摊平操作后的 $a_{mid}$ 应当不小于进行摊平操作前的 $a_{mid}$，二分时只判断这个条件。需要一个支持区间赋值和区间求和的线段树。

时间复杂度 $O(n \log ^2 n)$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int l,r;long long w,m;}s[800'005];
long long a[200'005];
int n;
void build(int u,int l,int r){
    s[u].l=l,s[u].r=r,s[u].m=0ll;
    if(l==r) return s[u].w=a[l],void();
    build(u*2,l,(l+r)/2);
    build(u*2+1,(l+r)/2+1,r);
    s[u].w=s[u*2].w+s[u*2+1].w;
}
inline void mark(int u,long long k){
    s[u].m=k,s[u].w=(s[u].r-s[u].l+1)*k;
}
void pushdown(int u){
    mark(u*2,s[u].m),mark(u*2+1,s[u].m),s[u].m=0ll;
}
void update(int u,int l,int r,long long k){
    if(s[u].l>r||s[u].r<l) return;
    if(s[u].l>=l&&s[u].r<=r) return mark(u,k);
    if(s[u].m) pushdown(u);
    update(u*2,l,r,k),update(u*2+1,l,r,k);
    s[u].w=s[u*2].w+s[u*2+1].w;
}
long long query(int u,int l,int r){
    if(s[u].l>r||s[u].r<l) return 0ll;
    if(s[u].l>=l&&s[u].r<=r) return s[u].w;
    if(s[u].m) pushdown(u);
    return query(u*2,l,r)+query(u*2+1,l,r);
}
void solution(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=n-1;i>=1;i--) if(query(1,i,i)>query(1,i+1,i+1)){
        int l=i+1,r=n,aim=i+1;
        while(l<=r){
            int mid=(l+r)>>1;
            if((query(1,i,mid)+mid-i)/(mid-i+1)<query(1,mid,mid)) r=mid-1;
            else aim=mid,l=mid+1;
        }
        long long lk=query(1,i,aim)/(aim-i+1),rk=(query(1,i,aim)+aim-i)/(aim-i+1);
        if(lk==rk) update(1,i,aim,lk);
        else{
            int mid=aim-query(1,i,aim)%(aim-i+1);
            update(1,i,mid,lk),update(1,mid+1,aim,rk);
        }
    }
    long long u=0ll,d=LONG_LONG_MAX;
    for(int i=1;i<=n;i++){
        long long x=query(1,i,i);
        u=max(u,x),d=min(d,x);
    }
    cout<<u-d<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}