参考资料

代码

/* * 康拓展开树状数组优化O(nlogn)  * 给一个排列，返回排列的排名 */#include
     
      using namespace std;typedef long long ll;const int MOD=1e9+7,N=1e5+5;int sum[N],n,a[N];ll jc[N];int lowbit(int x){    return x&-x;}void add(int x,int k){    while(x <= n){	sum[x]=sum[x]+k;	x=x+lowbit(x);    }}int getsum(int x){    int ans=0;    while(x>=1){	ans=ans+sum[x];	x=x-lowbit(x);    }    return ans;}void solve(){    ll rank=1;    for(int i=1;i<=n;i++){	add(a[i],1);	int k=getsum(a[i]-1);	k=(a[i]-1)-k;	rank = (rank + (k*jc[n-i])) %MOD;    }    printf("%lld\n",rank);}int main(){    jc[1]=1;    for(int i=2;i<=N;i++){	jc[i]=jc[i-1]*i%MOD;    }    int _;    scanf("%d",&_);    while(_--) {	memset(sum,0,sizeof(sum));	scanf("%d",&n);	for(int i=1;i<=n;i++) scanf("%d",&a[i]);	solve();    }}