Solution - CF362C Insertion Sort

前面两位大佬用的都是 $O( n^2 \log n)$ 的树状数组解法，所以我想提出一个$ O(n^2) $ 的解法，欢迎指出问题。

首先，冒泡排序（或是英文题面中的插入排序）需要交换的次数就是逆序对的个数。

怎么证明呢？其实很好理解。我们假设所有数都加上了 $1$ ，也就是原数组变成了 $1...n$ 的一个排列。当你交换 $a_i$ 和 $a_{i+1}$ 时，这两个数肯定是一对逆序对。而同时这两个数又是挨在一起的，所以 $1...i-1$ 的所有数往后的逆序对不会改变， $i+2...n$ 往前的逆序对也不会改变，相当于就干掉了一个逆序对。所以每次交换干掉一个逆序对，也就是说逆序对的个数就是要交换的个数。

那么怎么求逆序对呢？对于本题的数据量暴力就行了。

同时我们可以通过递推记录一个 $L$ 数组和 $R$ 数组，其中 $L_{i,j}$ 表示前 $i$ 个数小于 $j$ 的个数， $R_{i,j}$ 表示前 $i$ 个数大于 $j$ 的个数。

递推关系式为：

$L_{i,j}=L_{i-1,j}+[A_i<j]$
$M_{i,j}=M_{i-1,j}+[A_i>j]$

其中 $[x]$ 当表达式 $x$ 为真是为 $1$ ，否则为 $0$ 。

记录完了之后我们就暴力枚举所有要交换的 $(i,j)$ 。对于每个 $(i,j)$ ，答案就是

$ori$
$-M_{i-1,A_i}-M_{j-1,A_j}-L_{j-1,A_i}+L_{i,A_i}$
$+M_{i-1,A_j}+M_{j-1,A_i}+L_{j-1,A_j}-L_{i,A_j}$

其中 $ori$ 表示原数组的逆序对总数。

有点类似于前缀和的思想。

然后我们发现，好像连逆序对都顺便求好了，第 $i$ 个数贡献的逆序对就是 $M_{i-1,A_i}$

然后就完成了。所以这道题其实就直接暴力就行了。

其实树状数组很快，所以 $O( n^2 \log n)$ 的算法不一定比这个慢。

$Code:$

#include<cstdio>
const int N=5e3+1;
int n,ori,A[N],L[N][N],M[N][N];
signed main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i){
		scanf("%d",&A[i]);++A[i];
		for (int j=1;j<=n;++j){
			L[i][j]=L[i-1][j]+(A[i]<j);
			M[i][j]=M[i-1][j]+(A[i]>j);
		}//递推求两个数组。
		ori+=M[i][A[i]];
		//计算逆序对。
	}
	int ans=ori,ansk=0;
	for (int i=1;i<=n;++i){
		for (int j=i+1;j<=n;++j){
			int p=ori-M[i-1][A[i]]-M[j-1][A[j]]-L[j-1][A[i]]+L[i][A[i]]
			         +M[i-1][A[j]]+M[j-1][A[i]]+L[j-1][A[j]]-L[i][A[j]];
			//计算：减掉原来的，加上现在的。
			if (ans>p) ans=p,ansk=1;
			else if (ans==p) ++ansk;
		}
	}
	printf("%d %d",ans,ansk);
	return 0;
}