学步园

题意：每次交换两个数，求排序所做的交换次数
题解：用归并排序求逆序数

#include <cstdio>

int a[500000], b[500000];
long long cnt, n;

void mergesort ( int l, int r )
{
	if ( l >= r ) return;

	int mid = ( l + r ) / 2;
	mergesort(l,mid);
	mergesort(mid+1,r);

	int i = l, j = mid+1, k = l;
	while ( i <= mid && j <= r )
	{
		if ( a[i] > a[j] )
		{
			b[k++] = a[j++];
			cnt += mid-i+1;/* a[i] > a[j], 表示出现了逆序对，此时由于a[i..m]是已经有序了，那么a[i+1], a[i+2], ... a[m]都是大于a[j]的， 都可以和a[j]组成逆序对，因此number += m - i + 1 */
		}
		else
			b[k++] = a[i++];
	}
	while ( i <= mid ) b[k++] = a[i++];
	while ( j <= r ) b[k++] = a[j++];
	for ( i = l; i <= r; i++ )
		a[i] = b[i];
}

int main()
{
	while ( scanf("%d",&n) && n != 0 )
	{
		for ( int i = 0; i < n; i++ )
			scanf("%d",&a[i]);
		cnt = 0;
		mergesort(0,n-1);
		printf("%lld\n",cnt);
	}
	return 0;
}