P12912

lsj2009 · 2025-09-18 14:19:05 · 题解

题解要么是倒着扫、要么是选择删数，但其实不断加数也能做！！

容易注意到，第 k=k_0+1 的答案肯定是在 k=k_0 的基础上新加入了一个物品。这个物品需要满足，其和在其之后的所有被选择物品 a_i 之和，需小于所有在其之前的未被选择物品的 a_i。记 b_i 为 a_i 减去所有 j\ge i 且 j 被选择的 a_j 之和，新选择一个物品就是前缀减。选取的新物品要满足 a_i<\min\limits_{1\le j<i}{b_j}。

如何找到新选择的物品？分块，一个物品不可以被选要么是被块内在其之前的元素限制，要么是被在其前面块中的元素限制， 最终新选的物品肯定是，对于每个块单独考虑时合法的 a_i 最小的物品之一。因为其 a_i 小，本身就优秀且关于在其之前块的限制也更松。

如此问题转换为动态维护每个块内部的最优解，并且对这个块打上一个 b_i 区间减的 tag 后仍然可以获知答案。直接对于每个块维护一个单调栈就完了：a_i 递增，还有一个关于 tag 达到什么值这个 i 就选不了了的 deadline，也递增，查询时二分即可，重构时也只需要再扫一遍块是 \mathcal{O}(B) 的。复杂度 \mathcal{O}\left(n\left(B+\frac{n}{B}\log{B}\right)\right)，取 B=\sqrt{n\log{n}}，得最终复杂度为 \mathcal{O}(n\sqrt{n\log{n}})，常数较小可以通过。

#include<bits/stdc++.h>
// #define int long long
#define ll long long
#define ull unsigned long long
#define ld double
#define PII pair<int,int>
#define umap unordered_map
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define chkmin(a,b) a=min(a,b)
#define chkmax(a,b) a=max(a,b)
#define cl(f,x) memset(f,x,sizeof(f))
#define lg(x) (31-__builtin_clz(x))
using namespace std;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
void file_IO() {
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
}
bool M1;
const int N=5e5+5,B=1.5e3,M=B+5,K=N/B+5;
int l[K],r[K],cnt[K],bl[N],a[N],b[N],len[K],tag[N],mn[K];
PII t[K][M],d[M];
bool used[N];
inline bool empty(int k) {
    return r[k]-l[k]+1==cnt[k];
}
inline void rebuild(int k) {
    if(empty(k)) {
        mn[k]=INF;
        return;
    }
    mn[k]=INF;
    int tot=0;
    rep(i,l[k],r[k]) {
        if(used[i])
            continue;
        if(mn[k]>a[i]) {
            int x=mn[k]==INF? INF:mn[k]-a[i];
            while(tot&&d[tot].first<=x)
                --tot;
            d[++tot]=make_pair(x,i);
        }
        b[i]-=tag[k];
        chkmin(mn[k],b[i]);
    }
    tag[k]=0;
    len[k]=tot;
    per(i,tot,1)
        t[k][tot-i+1]=d[i];
}
inline int query(int k) {
    if(empty(k))
        return -1;
    int p=upper_bound(t[k]+1,t[k]+len[k]+1,make_pair(tag[k],INF))-t[k];
    if(p==len[k]+1)
        return -1;
    else
        return t[k][p].second;
}
void solve() {
    int n;
    scanf("%d",&n);
    rep(i,1,n)
        scanf("%d",&a[i]),b[i]=a[i];
    int tot=(n-1)/B+1;
    rep(i,1,tot) {
        l[i]=(i-1)*B+1;
        r[i]=min(i*B,n);
        rep(j,l[i],r[i])
            bl[j]=i;
        rebuild(i);
    }
    ll res=0;
    rep(_,1,n) {
        int mnv=INF,p=-1;
        rep(i,1,tot) {
            int x=query(i);
            if(x!=-1&&a[x]<mnv&&(p==-1||a[x]<a[p]))
                p=x;
            if(mn[i]!=INF)
                chkmin(mnv,mn[i]-tag[i]);
        }
        res+=a[p];
        printf("%lld ",res);
        used[p]=true; ++cnt[bl[p]];
        rep(i,l[bl[p]],p)
            b[i]-=a[p];
        rebuild(bl[p]);
        rep(i,1,bl[p]-1)
            tag[i]+=a[p];
    }
    puts("");
}
bool M2;
// g++ P12912.cpp -std=c++14 -O2 -Wall -o P12912
signed main() {
    // file_IO();
    int testcase=1;
    // scanf("%d",&testcase);
    while(testcase--)
        solve();
    fprintf(stderr,"used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
    fprintf(stderr,"used memory = %dMB\n",(signed)((&M2-&M1)/1024/1024));
    return 0;
}