$\huge{\texttt{Description}}$

1.$O(n!)$ 想法

首先，$N\le 8$，所以说标准做法就是一个一个枚举。

你当然可以用 C++ 的 STL 中的 next_permutation() 函数来完成，这里我们讲不用这个函数的方法。

假设已经有了一个序列：$1,3,4,2,5,6$。我们要求它的后继。

第一步，看最后一位。如果最后一位比倒数第二位大，就直接交换；

否则，就看倒数第二位，直到出现一位 $x$ 比前一位大的时候，就将 $x-1$ 位到 $n$ 位排序即可。

到此为止题目已经解决。但是，还有没有更好的解法？如果 $N\le 10^4$ 呢？

2.$O(n^2)$ 想法

我们定义数组 la[i],lb[i]，分别表示 $a_i$ 在 $a_i-a_n$ 中的排名和 $b_i$ 在 $b_i-b_n$ 的排名。比如 $a=\{1,3,2,4,5,6\}$，那么 $la=\{ 1,2,1,1,1,1\}$。

这一个处理是 $O(n^2)$ 的效率，也是程序的瓶颈。

下一步，从小到大遍历 $1-n$，更新答案，加上 $(la_i-lb_i)\times (n-i)!$。也就是说，我们更新了前 $i$ 位和 $a,b$ 数组相同，后 $n-i$ 位都是 $a$ 数组的数的编号之差。

如果我们预处理阶乘，那么复杂度就是 $O(n)$。

3.$O(n\log n)$ 想法

注意到我们每次处理 $la,lb$ 的时候都会重复枚举，这样肯定耽误时间。

我们可以理解为，$la_i=a_i-\text{a[1]到a[i-1]中比a[i]小的个数}$。

这样答案就非常显然了：用树状数组维护。

或者线段树也行，不过我懒得写。

这样的话就能保证每次更新的时候是 $\log n$ 的效率，常数的增加没有过多影响。

$\huge{\texttt{Code}}$

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n;
int a[N],b[N];
int t[N];
int cal[N];
int ans=0;
//树状数组基本三件套
int lowbit(int x){
	return x&(-x);
}
void add(int pos){
	for(int i=pos;i<=n;i+=lowbit(i))
		t[i]++;
}
int query(int pos){
	int ret=0;
	for(int i=pos;i>=1;i-=lowbit(i))
		ret+=t[i];
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		add(a[i]);
		int prev=query(a[i]-1);
		a[i]-=prev;//我们将la[]代替a[]，处理方式上面说了
	}
	memset(t,0,sizeof(t));
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		add(b[i]);
		int prev=query(b[i]-1);
		b[i]-=prev;//处理lb[]数组，同la[]
	}
    //预处理cal数组，其中cal[i]=i!
	cal[0]=1;
	for(int i=1;i<=n;i++) cal[i]=cal[i-1]*i;
    //按照解答中所说进行答案更新
	for(int i=1;i<=n;i++){
		ans+=(a[i]-b[i])*cal[n-i];
	}
    //注意到b数组的序号可能多于a数组，所以要取绝对值
	printf("%d\n",abs(ans));
	exit(0);
}

写一篇题解不容易，看完记得点个赞哦~