P12912

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

容易注意到，第

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}})

，常数较小可以通过。

CPP

#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;
}

文章操作

相关推荐

评论

P12912