pku2299.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>

int a[500001], b[500001];
__int64 change;

void merge(int, int, int);

void mergeSort(int first, int last)
{
        if(first < last) {
                int mid = (first + last) / 2;
                mergeSort(first, mid);
                mergeSort(mid+1, last);
                merge(first, mid, last);
        }
}
void merge(int p, int q, int r)
{
        int i, j = 0;
        int beginA = p, endA = q, beginB = q+1, endB = r;
        
        while(beginA <= endA && beginB <= endB) {
                if(a[beginA] <= a[beginB]) {
                        b[j++] = a[beginA++];
                } else {
                        b[j++] = a[beginB++];
                        change += q - beginA + 1;
                }
        }
        while(beginA <= endA) {
                b[j++] = a[beginA++];
        }
        while(beginB <= endB) {
                b[j++] = a[beginB++];
        }
        for(i = 0; i < j; i++) {
                a[p+i] = b[i];
        }
}

int main()
{
	int N, i;

	while (scanf("%d", &N) != -1 && N)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d", &a[i]);
		}
		change = 0;
		mergeSort(0, N - 1);
		printf("%I64d\n", change);
	}
	return 0;
}