逆序对满足两个条件， i < j 和 ai > aj

归并可以求逆序对， 因为是按顺序加入， 所以右区间加入的时候， 左区间的数满足 i < j， 然后左边还没有加入的数肯定比当前的a[q]要大， 应该是按大小加入的， 所以满足ai >ａｊ，　所以这个时候计数器可以加上左区间还没加入数的个数，　即ｍ－ｐ，　注意是左闭右开区间，　所以ｍ－ｐ不用加一。

 

#include
    
     #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std; const int MAXN = 112;int a[MAXN], cnt, n; void merge_sort(int l, int r)  //这里是左闭右开区间， 区间分两段不需要加一减一 {	if(l + 1 >= r) return;	int m = (l + r) >> 1;           // l与r的平均数 	merge_sort(l, m); merge_sort(m, r); //先递归， 再求解 		int i = l, j = m, t[MAXN];	REP(k, l, r)	{		if(j >= r || i < m && a[i] <= a[j]) t[k] = a[i++]; //右区间空或者左区间非空且a[p]更优的时候加入 		else t[k] = a[j++], cnt += m - i;	}	REP(i, l, r) a[i] = t[i];} int main(){	scanf("%d", &n);	REP(i, 0, n) scanf("%d", &a[i]);	merge_sort(0, n);	REP(i, 0, n) printf("%d ", a[i]);	printf("\n%d\n", cnt);	return 0;}