题解 P6035 【Ryoku 的逆序对】

feecle6418 · 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;
}