归并排序是一种稳定排序。想要知道什么是归并排序要先知道就要先了解分治与递归的思想。

参考我的博客:click here !!!
归并排序求逆序数的思想就是,利用递归不挺的将一列数分成两部分,然后cnt加上每一个被分开的部分中的逆序数,在不停的分治的时候也进行了排序。最后求出被分开的两部分中的总逆序数。

例如 2 4 3 1 先分成 2 4 和 3 1

然后2 4进一步分成 2 和 4,3 1进一步分成 3 1并且进行一次交换变成 1 3

最后递归返回就变成了 2 4 1 3,这个数列中逆序数为3,然后再加上 3 1中的1,结果就为4.

题目: 逆序数

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。给出一个整数序列,求该序列的逆序数。

Input

第1行:N,N为序列的长度(n <= 50000) 
第2 - N + 1行:序列中的元素(0 <= Aii <= 10^9)

Output

输出逆序数

Sample Input

4
2
4
3
1

Sample Output

4
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

vector<int> v;
LL merge_sort( vector<int> & v )
{
	int n = v.size();
	if( n <= 1 )
		return 0;
	LL cnt = 0;
	vector<int> vb(v.begin(), v.begin() + n/2);
	vector<int> ve(v.begin() + n/2, v.end());
	cnt += merge_sort(vb);
	cnt += merge_sort(ve);
	int a, b, c;
	a = b = c = 0;
	while( a < n )
	{
		if( b < vb.size() && (c == ve.size() || vb[b] <= ve[c]) )
			v[a++] = vb[b++];
		else
		{
			v[a++] = ve[c++];
			cnt += n/2 - b;
		}
	}
	return cnt;
}

int main()
{
	int n, num;
	while( ~scanf("%d", &n) )
	{
		v.clear();
		for( int i=0; i<n; i++ )
		{
			scanf("%d", &num);
			v.push_back(num);
		}
		printf("%lld\n", merge_sort(v));
	}


	return 0;
}