在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。
比如 1 3 2 的逆序数就是1。
输入 第一行输入一个整数T表示测试数据的组数（1<=T<=5) 每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000） 随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。 数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。 输出 输出该数列的逆序数 样例输入 2 2 1 1 3 1 3 2 样例输出 0 1 #include <stdio.h> #include <string.h> long long a[1000005]; long long b[1000005]; long long count; void Merge(long long *a,int L,int mid,int R) { int k=L; int i=L,j=mid+1; while(i<=mid && j<=R) { //较小的元素，存入temp临时数组中 if(a[i]<=a[j]) b[k++]=a[i++]; else//出现逆序对 { b[k++]=a[j++]; count+=mid-i+1; } } //假如第1个有序区仍有剩余，则直接全部复制到 b数组 while(i<=mid) b[k++]=a[i++]; //同理，有剩余则放到 b数组 while(j<=R) b[k++]=a[j++]; //将排好的序列，重新放到原数组的 L和 R区间 for(int t=L;t<=R;t++) a[t]=b[t]; } void MergeSort(long long *a,int L,int R) { if(L<R) { int mid = (L+R)/2; MergeSort(a,L,mid); MergeSort(a,mid+1,R); Merge(a,L,mid,R); } } int main() { int T,N,i; scanf("%d",&T); while(T--) { scanf("%d",&N); for(i=0;i<N;i++) scanf("%lld",&a[i]); count=0; MergeSort(a,0,N-1); printf("%lld\n",count); } return 0; }