其实以前我对逆序对并不是太了解，也只知道暴力求法，今天看了下怎么求逆序对个数的三种方法。

1. 暴力：时间复杂度$O(n^2)$，空间复杂度$O(n)$。常数为1.

很简单的暴力，$for(i→[1,n])$，$for(j→[1,i))$，暴力枚举统计即可。

2. 树状数组 时间复杂度$O(nlogn)$，空间复杂度$O(n)$，其中时间复杂度常数为2（因为需要快排一遍），空间复杂度的常数为4（离散+树状数组+原数+原数的位置($pos$)）。

怎么做呢？首先树状数组元素都是0，每次在离散后的位置上插入一个数1，统计在这个数前面的1有多少个，统计即可。

这篇文章写的比较清楚：传送门

代码：

# include <stdio.h>
# include <algorithm>
# include <stdlib.h>
using namespace std;
int c[1000010],n;
struct ps {
	int pos,data;
}a[1000010];
int d[1000010]; //离散后的数 
inline int lowbit(int x) {return x&(-x);}
inline int cmp(struct ps a,struct ps b) {
	return a.data<b.data;
}
inline void modify(int pos,int x) {
	while(pos<=n) {
		c[pos]+=x;
		pos+=lowbit(pos);
	}
}
inline int query(int pos) {
	int sum=0;
	while(pos>0) {
		sum+=c[pos];
		pos-=lowbit(pos);
	}
	return sum;
}
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i].data),a[i].pos=i;
	sort(a+1,a+n+1,cmp);
	int ord=1;
	d[a[1].pos]=ord;
	for (int i=2;i<=n;++i) {
		if(a[i].data==a[i-1].data) d[a[i].pos]=ord;
		else d[a[i].pos]=++ord;
	}
	long long ans=0;
	for (int i=1;i<=n;++i) {
		modify(d[i],1);
		ans += i-query(d[i]); 
	}
	printf("%lld\n",ans);
	return 0;
}

3. 归并排序求逆序对。

时间复杂度$O(nlogn)$，空间复杂都$O(n)$，常数为2.

归并的时候找到有交叉的部分进行统计即可。

# include <stdio.h>

using namespace std;

int n, a[1000010];
int tmp[1000010];
long long ans=0;

inline void merge(int l,int mid,int r) {
	int i=l, j=mid+1, k=l;
	while(i<=mid&&j<=r) {
		if(a[i]>a[j]) {
			tmp[k++]=a[j++];
			ans+=mid-i+1;	
		} else tmp[k++]=a[i++];
	}
	while(i<=mid) tmp[k++]=a[i++];
	while(j<=r) tmp[k++]=a[j++];
	for (int i=l;i<=r;++i) a[i]=tmp[i];
}

void mergesort(unsigned int l,unsigned int r) {
	if(l<r) {
		int mid=(l+r)>>1;
		mergesort(l,mid);
		mergesort(mid+1,r);
		merge(l,mid,r);
	}
}
int main() {
	scanf("%d",&n);
	for (int i=0;i<n;++i) scanf("%d",&a[i]);
	mergesort(0,n-1);
	printf("%lld\n",ans);
	return 0;
}