P1908 逆序对
题目描述
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
Update：数据已加强。
输入格式
第一行，一个数 $n$，表示序列中有 $n$ 个数。
第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。
输出格式
输出序列中逆序对的数目。
输入输出样例 #1
输入 #1
6
5 4 2 6 3 1输出 #1
11
说明/提示
对于 $25%$ 的数据，$n \leq 2500$。
对于 $50%$ 的数据，$n \leq 4 \times 10^4$。
对于所有数据，$1 \leq n \leq 5 \times 10^5$。
应该不会有人 $O(n^2)$ 过 50 万吧 —— 2018.8 chen_zhe。
`#include<bits/stdc++.h>
using namespace std;
define K 500005
int a[K], b[K];
long long int ans;
// 归并排序做
void Guibing(int x, int y) {
if (x == y)
return;
int mid = (x + y) / 2, i = x, j = mid + 1, k = x;
Guibing(x, mid);
Guibing(mid + 1, y);
while (i <= mid && j <= y) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
} else {
b[k++] = a[j++];
ans += mid - i + 1;
}
}
// 处理左子数组剩余元素
while (i <= mid) {
b[k++] = a[i++];
}
// 处理右子数组剩余元素
while (j <= y) {
b[k++] = a[j++];
}
// 将辅助数组元素复制回原数组
for (int m = x; m <= y; m++) {
a[m] = b[m];
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
Guibing(1, n);
cout << ans;
return 0;
} 看大佬的半天才会点，下面是收获，下次再做时更新。 首先是归并排序是有递归和非递归两种方法，我这里只大概懂递归版，递归是自顶向下的，原理就是分割和归并两个大步骤， 以数列范围/2为中间值，向下取整，分成两块，然后分别定义几个特殊位置的变量，i为x为左区间第一位，j为右1，k用来临时数组赋值。 在分到最小区间，内数量为1，为有序，之后不断合并，Guibing(x, mid);Guibing(mid + 1, y);，最终分成两个大块，期间不断进行两个区间中最小数的比较， 小的放临时数组，个人觉得这个里面的i++等很妙，最终ans += mid - i + 1;原理是排好的两区间是有序，若左有大于右区间的，则左那个数后的数全大于右那个比较的数 while (i <= mid && j <= y) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
} else {
b[k++] = a[j++];
ans += mid - i + 1;
}
}`
实现逆序对的计数。
剩下的几个while用于将多余的没有比对的两区间的数分别赋值临时数组，以左为先，最后再覆盖到原数组中。
归并完成。