时间限制：2000 ms | 内存限制：65535 KB
难度：5
描述
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
现在，给你一个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 <iostream>//归并排序。。。。。。 #include <cstdio> #include <cstring> using namespace std; long a[1000008]; int m; long long sum;//注意这里要是long long型的 void merge_sort(long *a, int x, int y, long *b) { if (x < y) { int m = (x + y) / 2; merge_sort(a, x, m, b); merge_sort(a, m + 1, y, b); int i = x, j = m + 1; int k = x; while (i <= m && j <= y) { if (a[i] <= a[j]) b[k++] = a[i++]; else { sum = sum + m - i + 1; b[k++] = a[j++]; } } while (i <= m) b[k++] = a[i++]; while (j <= y) b[k++] = a[j++]; for (int i = x; i < k; i++) a[i] = b[i]; } } int main() { long b[1000000] = {0}; int n; scanf("%d", &n); while (n--) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); sum = 0; scanf("%d", &m); for (int i = 0; i < m; i++) scanf("%ld", &a[i]); merge_sort(a, 0, m - 1, b); printf("%lld\n", sum); } return 0; }
