【题解】UVA10810-归并排序求逆序对

#### 在解题之前，先让我们来看一看本题会用到而萌新可能不懂的几个事项： 本题大意：对于给定的无序数组，求出经过最少多少次相邻元素的交换之后，可以使数组从小到大有序 对于逆序对的解释：两个数（a, b）的排列，若满足a > b，则称之为一个逆序对 归并排序的思想：先把每个数看成一段，然后两两合并成一个较大的有序数组，再把较大的两两合并，直到最后成为一个有序数组 归并排序复杂度：$ O(nlogn) $ #### 接下来就是我们解题的步骤了: （P.S：听说这道题还是到数状树组的板子题，可惜本蒟蒻想了半天想不出来数状树组解法，于是就来了一发归并排序） 根据排序算法，我们知道如果相邻的两个元素满足前一个大于后一个便会交换一次，由于题目要求排序后是单调递增，所以我们可以将这道题看做求原数组逆序对的数量 举一个归并排序的例子： 假设初始数组为4 2 1 3 先把每一个数单独分成一组，即(4) (2) (1) (3) 接着两两合并，即(2 4) (1 3) 最后合成一个有序的数组，即(1 2 3 4) 不难发现，在排序过程中，若某个数向前移动了N位，则必定存在N个逆序数,如上面例子中，数字1由原先的第三位移到了第一位，前移了两位，则存在(2 1)和(4 1)两个逆序 而根据题意，我们只需要在归并排序的过程中把这个数记下来即可 接下来上一下代码（自测90ms、~~毒瘤的~~卡常与优化后60ms，算是比较快的方法） ```cpp #include<cstdio> using namespace std; #define ll long long ll ans[500010], mem[500010], anss; int n; void merge(int lo, int mid, int hi){ int i = lo, e = mid + 1, k =lo; while(i <= mid && e <= hi){ if(ans[i] <= ans[e]) mem[k++] = ans[i++]; else anss += e - k, mem[k++] = ans[e++]; /*上面的ans += e - k 就是求逆序对和的过程*/ } while(i <= mid) mem[k++] = ans[i++]; while(e <= hi) mem[k++] = ans[e++]; for(i = lo; i <= hi; ++i) ans[i] = mem[i]; } void merge_sort(int x, int y){ if(x < y){ int mid = (x + y) / 2; merge_sort(x, mid); merge_sort(mid + 1, y); merge(x, mid, y); } } int main(){ while (scanf("%d", &n) != EOF && n > 0) { anss = 0; for (int i = 0; i < n; ++i) { scanf("%lld", ans + i); } merge_sort(0, n - 1); printf("%lld\n", anss); } return 0; } ```