自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 22:16:44，当前版本为作者最后更新于2020-01-31 19:56:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一问，每个为 -1 的位置 $i$ 都会造成 $n-i+1$ 种可能，由乘法原理，乘起来就是答案。重点在第二问。

贪心地从前往后拼凑。假如 $a$ 之后有 $b$ 个比他小，就从小到大找第 $b+1$ 个还没被选到的数 $x$，并令 $a\leftarrow x$。假如是 -1，就找当前没有选到的最小值。

现在的问题是怎么维护“第 $k$ 个还没被选到的数”。可以使用树状数组，在树状数组上倍增往上跳，同时累加前缀和，加到 $k+1$ 时就是答案。

这样说很抽象，看代码：

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int c[1000005],a[1000005],ans[1000005],used[1000005],n,now=1,s=1;
void Update(int x,int k) {
	while(x<=n)c[x]+=k,x+=x&-x;
}
int Find(int x) {
	int ret=0,now=0;
	for(int i=19; i>=0; i--) {
		if((ret+(1<<i))<=n&&now+c[ret+(1<<i)]<=x)ret+=(1<<i),now+=c[ret];//		cout<<now<<' '<<ret<<endl;
	}
	return ret+1;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]),Update(i,1);
		if(a[i]>n-i)return puts("0"),0;
		if(a[i]==-1)s=1ll*s*(n-i+1)%mod;
	}
	printf("%d\n",s);
	for(int i=1;i<=n;i++){
		if(~a[i]){
			ans[i]=Find(a[i]);
			Update(ans[i],-1);
			used[ans[i]]=1;
		}
		else {
			while(used[now])now++;
			ans[i]=now;
			Update(ans[i],-1);
			used[ans[i]]=1;
		}
		printf("%d ",ans[i]);
	}
	return 0;
}