水题，没啥好说的，归并排序求逆序对
代码如下：
#include<stdio.h>
#include<stdlib.h>
int a[1000000], b[1000000];
int num;void mix(int *a,int *n,int left,int mid,int right)
{int i = left;int j = mid + 1;int k = left;while (i < mid + 1 && j < right + 1){if (a[i] <= a[j])b[k++] = a[i++];else{b[k++] = a[j++];num += mid - i + 1;}}while (i != mid + 1)b[k++] = a[i++];while (j != right +1 )b[k++] = a[j++];for (i = 0; i < k; i++)a[i] = b[i];}void sever(int *a,int *b,int left,int right)
{int mid;if (left < right){mid = (left + right) / 2;sever(a, b, left, mid);sever(a, b, mid + 1, right);mix(a, b, left, mid, right);}
}int main()
{int m,n,i,j,count=1;scanf("%d", &m);for ( i = 0; i < m; i++){num = 0;scanf("%d", &n);for (j = 0; j < n; j++)scanf("%d", &a[j]);sever(a, b, 0, n - 1);printf("Scenario #%d:\n", count++);printf("%d\n", num);printf("\n");}return 0;
}