Lang:G++
Edit12345678910111213141516171819202122232425262728293031#include <iostream>#include <string.h>#include <stdio.h>using namespace std;const int N = 100000;long long total;//逆序数long *swap_space= new long[N];//归并排序的交换空间void merge(long a[], long begin, long mid,long end){long i = begin;long j = mid + 1;long k = begin;while(i <= mid && j <= end){if(a[i] < a[j]){swap_space[k++] = a[i++];}else{swap_space[k++] = a[j++];total += (mid - i + 1);//total is the reverse count}}while(i <= mid)swap_space[k++] = a[i++];while(j <= end)swap_space[k++] = a[j++];for(i = begin; i <= end; i++){a[i] = swap_space[i];}