AtCoder Grand Contest 023 E - Inversions

Description

给出长度为 (n) 序列 (A_i),求出所有长度为 (n) 的排列 (P),满足 (P_i<=A_i),求所有满足条件的 (P) 的逆序对数之和
题面

Solution

设 (c[k]) 表示 (A_i>=k) 的个数,那么对于所有的 (c[k]>=(n-k+1)),不满足则不合法
把 (c[k]) 变为 (c[k]-(n-k),)总方案就是 (Pi c[k])
考虑逆序对 ((i,j)) 的贡献
如果满足 (A_i<=A_j) ,那么把 (A_j) 变成 (A_i),然后 ((i,j)) 作为逆序对的方案数就是合法排列的方案数除以 (2)
把 (A_j) 变成 (A_i) 之后,([A_i+1,A_j]) 这一个区间的 (c) 会减 (1),可以维护一个前缀积 (frac{c_i-1}{c_i}) 可以 (O(1)) 算出替换后的贡献
那么就可以树状数组维护一下每个数对的贡献了

对于 (A[i]>A[j]) 的情况,补集转换一下,总方案-把 (A_i) 替换成 (A_j) 的方案,然后和上面一样的做一遍就好了

#include<bits/stdc++.h>
using namespace std;
template<class T>void gi(T &x){
    int f;char c;
    for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
    for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}

const int N=2e5+10,mod=1e9+7;
inline int qm(int x,int k){
    int sum=1;
    while(k){
        if(k&1)sum=1ll*sum*x%mod;
        x=1ll*x*x%mod;k>>=1;
    }
    return sum;
}
int n,a[N],c[N],v0[N],R[N],tr[N],S;
inline void add(int x,int t){
    for(int i=x;i<=n;i+=(i&(-i)))tr[i]=(tr[i]+t)%mod;
}
inline int qry(int x){
    int ret=0;
    for(int i=x;i>=1;i-=(i&(-i)))ret=(ret+tr[i])%mod;
    return ret;
}
int main(){
  freopen("pp.in","r",stdin);
  freopen("pp.out","w",stdout);
  cin>>n;
  for(int i=1;i<=n;i++)gi(a[i]),c[a[i]]++;
  for(int i=n-1;i>=1;i--)c[i]+=c[i+1]-1;
  for(int i=1;i<=n;i++)if(c[i]<=0)return puts("0"),0;
  v0[0]=S=1;
  for(int i=1;i<=n;i++){
      v0[i]=1ll*v0[i-1]*(c[i]>1?c[i]-1:1)%mod*qm(c[i],mod-2)%mod;
      S=1ll*S*c[i]%mod;
  }
  R[n]=n;
  for(int i=n-1;i>=1;i--)R[i]=c[i+1]>1?R[i+1]:i;
  int ans=0,t;
  //A[i]<=A[j]
  for(int i=n;i>=1;i--){
      t=(qry(R[a[i]])-qry(a[i]-1)+mod)%mod;
      ans=(ans+1ll*t*qm(v0[a[i]],mod-2))%mod;
      add(a[i],v0[a[i]]);
  }
  //A[i]>A[j]
  R[1]=1;
  memset(tr,0,sizeof(tr));
  for(int i=2;i<=n;i++)R[i]=c[i]>1?R[i-1]:i;
  for(int i=n;i>=1;i--){
      t=(qry(a[i]-1)-qry(R[a[i]]-1)+mod)%mod;
      ans=(ans-1ll*t*v0[a[i]]%mod+mod)%mod;
      add(a[i],qm(v0[a[i]],mod-2));
  }
  ans=1ll*ans*qm(2,mod-2)%mod;
  memset(tr,0,sizeof(tr));
  for(int i=1;i<=n;i++){
      ans=(1ll*ans+i-1-qry(a[i])+mod)%mod;
      add(a[i],1);
  }
  ans=1ll*ans*S%mod;
  cout<<ans<<endl;
  return 0;
}