数组中的逆序对

http://www.acmerblog.com/offer09-2527.html
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数

直接的做法是逐个统计，复杂度是N^2，可以利用归并排序的思想，在排序过程中统计逆序对的个数。
时间复杂度依然是 N*Log(N)。 可以从代码中看到，只是比归并排序多了一句代码：cnt += (end-j+1).
由于最终个数可能超过int，这里用long long

13	int n, arr[100010], tmp[100010];

14

15	//归并排序，过程中 统计逆序数

16	ll merge(int start, int mid, int end){

17	ll cnt = 0;

18	int i = start, j = mid+1, k = start;

19	while( i<=mid && j<= end){

20

//从大到小排序

21	if(arr[i] > arr[j]){

22	cnt += (end-j+1); //右面剩下的都是逆序

23	tmp[k++] = arr[i++];

24

}else{

25	tmp[k++] = arr[j++];

26

}

27

}

28	while(i<=mid) tmp[k++] = arr[i++];

29	while(j<=end) tmp[k++] = arr[j++];

30	for(int i=start; i<=end; i++) arr[i] = tmp[i];

31	return cnt;

32

}

33	ll inversePairs(int start, int end){

34	ll cnt = 0;

35	if(start < end){

36	int mid = (start + end)/2;

37	cnt += inversePairs(start, mid); //左半部分 逆序对数量

38	cnt += inversePairs(mid+1, end); //右半部分

39	cnt += merge(start, mid, end); //合并两部分，并计算数量

40

}

41	return cnt;

42

}

43	int main() {

44	//freopen("in.txt", "r", stdin);

45	while( scanf("%d", &n) != EOF){

46	for(int i=0; i<n; i++) scanf("%d", &arr[i]);

47	ll ans = inversePairs(0, n-1);

48	printf("%lld\n",ans);

49

}

50

return 0;

51

}