Codeforces

Luogu

分析

考虑一个贪心，即每次取贡献最大的一个，这里的贡献是 $k_i\times a_i+b_i$，其中 $k_i$ 表示前面选了的数量，$b_i$ 表示后面选了的 $a_i$ 的和。

那么我们相当于要维护一些直线，支持区间斜率加、截距加和求全局最大值。

考虑分块，对每块维护一个上凸壳，散块修改后重构、整块打标记即可。注意要把当前选出来的数删掉。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=350;

int n,a[N],p[N];
int B,bl[N],L[M],R[M];
ll w[N],k[M],b[M];
int q[N],qh[M],qt[M],del[N];

double slope(int i,int j) {
    if (a[i]==a[j]) return w[i]<w[j]?1e50:-1e50;
    else return 1.0*(w[j]-w[i])/(a[j]-a[i]);
}
ll calc(int x) { return w[x]+k[bl[x]]*a[x]+b[bl[x]]; }
void build(int x) {
    for (int i=L[x];i<=R[x];++i) w[i]+=k[x]*a[i]+b[x];
    k[x]=b[x]=0; int h=L[x],t=L[x]-1;
    for (int i=L[x];i<=R[x];++i) {
        if (del[p[i]]) continue;
        while (h<t&&slope(q[t-1],q[t])<slope(q[t],p[i])) --t;
        q[++t]=p[i];
    }
    qh[x]=h,qt[x]=t;
}
pair<ll,int> qmax(int x) {
    int& h=qh[x],t=qt[x];
    while (h<t&&calc(q[h])<calc(q[h+1])) ++h;
    if (h>t) return make_pair(0ll,0);
    else return make_pair(calc(q[h]),q[h]);
}

int main() {
    n=read(); B=sqrt(n);
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n;++i) bl[i]=(i-1)/B+1;
    for (int i=1;i<=bl[n];++i) {
        L[i]=(i-1)*B+1,R[i]=min(i*B,n);
        for (int j=L[i];j<=R[i];++j) p[j]=j,w[j]=a[j];
        sort(p+L[i],p+R[i]+1,[](int x,int y) { return a[x]<a[y]; });
        build(i);
    }
    ll ans=0;
    while (1) {
        pair<ll,int> mx=make_pair(0ll,0);
        for (int i=1;i<=bl[n];++i) mx=max(mx,qmax(i));
        if (!mx.first) break;
        ans+=mx.first; int p=mx.second;
        for (int i=1;i<bl[p];++i) b[i]+=a[p];
        for (int i=L[bl[p]];i<p;++i) w[i]+=a[p];
        for (int i=p+1;i<=R[bl[p]];++i) w[i]+=a[i];
        for (int i=bl[p]+1;i<=bl[n];++i) ++k[i];
        del[p]=1; build(bl[p]);
    }
    printf("%lld\n",ans);
    return 0;
}