poj 2299 Ultra-QuickSort

http://162.105.81.212/JudgeOnline/problem?id=2299

归并排序, 在"归并"时计算逆序数的个数.

ret += mid-first1+1;

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 500000
__int64 ret;
int a[MAX], tmp[MAX];
void Merge(int *a, int first, int mid, int last)
{
	int first1, last1, first2, last2, k, i;
	first1 = first, last1 = mid;
	first2 = mid + 1, last2 = last;
	k = 0;
	while(first1 <= last1 && first2 <= last2)
	{
		if(a[first1] < a[first2])
			tmp[k++] = a[first1++];
		else
		{
			tmp[k++] = a[first2++];
			ret += mid-first1+1;
		}
	}
	while(first1 <= last1)
		tmp[k++] = a[first1++];
	while(first2 <= last2)
		tmp[k++] = a[first2++];
	for(i=0; i<(last-first+1); i++)
		a[first+i] = tmp[i];
}

void MergeSort(int *a, int first, int last)
{
	int mid = 0;
	if(first < last)
	{
		mid = (first+last)>>1;
		MergeSort(a, first, mid);
		MergeSort(a, mid+1, last);
		Merge(a, first, mid ,last);
	}
}

int main()
{
	int n, i;
	while(scanf("%d", &n), n)
	{
		for(i=0; i<n; i++)
			scanf("%d", a+i);
		ret = 0;
		MergeSort(a, 0, n-1);
		printf("%I64d/n", ret);
	}
	return 0;
}