题目链接：
题意就是求冒泡排序的交换次数，显然直接冒泡会超时，所以需要高效的方法求逆序数。
利用归并排序求解，内存和耗时都比较少， 但是有编码难度。。
二叉排序树，内存巨大，时间复杂度高，但是非常好写。。
归并排序版本：
1 #include2 #include 3 long long merge_arr(int arr[], int first, int mid, int last, int tmp[]) 4 { 5 long long ret = 0; 6 int i = first, j = mid+1, k = 0; 7 while(i <= mid && j <= last) 8 { 9 if(arr[i] < arr[j])10 {11 tmp[k++] = arr[i++];12 ret += j - mid - 1;13 }14 else tmp[k++] = arr[j++];15 }16 while(i <= mid)17 {18 tmp[k++] = arr[i++];19 ret += last - mid;20 }21 while(j <= last)22 tmp[k++] = arr[j++];23 for(i = 0; i < k; i++)24 arr[first+i] = tmp[i];25 return ret;26 }27 28 long long merge_sort(int arr[], int first, int last, int tmp[])29 {30 long long ret = 0;31 if(first < last)32 {33 int mid = (first + last) / 2;34 ret += merge_sort(arr, first, mid, tmp);35 ret += merge_sort(arr, mid+1, last, tmp);36 ret += merge_arr(arr, first, mid, last, tmp);37 }38 return ret;39 }40 41 int n, num[500010], tmp[500010];42 int main()43 {44 while(scanf("%d", &n) != EOF && n)45 {46 for(int i = 0; i < n; i++)47 scanf("%d", &num[i]);48 printf("%I64d\n", merge_sort(num, 0, n-1, tmp));49 }50 return 0;51 }
二叉排序树版本：
1 #include2 #include 3 4 struct node 5 { 6 int data, cnt_right; 7 struct node *left, *right; 8 }; 9 10 long long ans;11 12 void build(struct node *&p, int k)13 {14 if(p == NULL)15 {16 p = (struct node *)malloc(sizeof(struct node));17 p->data = k;18 p->cnt_right = 0;19 p->left = p->right = NULL;20 }21 else if(p->data > k)22 {23 ans += p->cnt_right + 1;24 build(p->left, k);25 }26 else27 {28 p->cnt_right++;29 build(p->right, k);30 }31 }32 33 void del(struct node *p)34 {35 if(p == NULL)return;36 del(p->left);37 del(p->right);38 free(p);39 }40 41 int main()42 {43 int n, x;44 while(scanf("%d", &n) != EOF && n)45 {46 ans = 0;47 struct node *root = NULL;48 while(n--)49 {50 scanf("%d", &x);51 build(root, x);52 }53 del(root);54 printf("%I64d\n", ans);55 }56 return 0;57 }