归并排序统计逆序对的数量

788. 逆序对的数量 - AcWing题库

昨天刚好做到这题，发现网上题解都讲的不是很详细，于是决定自己手写一篇。

归并排序能统计逆序对的数量

为什么归并排序能统计逆序对数量？？？

归并排序的特点是，以mid，mid+1为分界，对两边分别进行排序

借助递归的性质先将两边都从小到大排好序，之后再进行合并

一旦发现左边有一个数字比右边大，从这个数字开始一直到mid都会比右边的这个数字大

这里是相对这个数字而言，因此不会记重

每一层最后都合并回去排序好的结果，给下一层用

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N = 2e5 + 10;
 7 
 8 int n;
 9 ll ans;
10 int a[N];
11 int q[N];
12 
13 void merge_sort(int l, int r)
14 {
15     if (l >= r)return;
16 
17     int mid = l + r >> 1;
18 
19     merge_sort(l, mid), merge_sort(mid + 1, r);
20 
21     int i = l, j = mid + 1;
22     int k = 0;
23 
24     while (i <= mid && j <= r)
25     {
26         if (a[i] <= a[j])
27         {
28             q[k++] = a[i++];
29         }
30         else
31         {
32             q[k++] = a[j++];
33 
34             ans += mid - i + 1;
35         }
36     }
37 
38     while (i <= mid)q[k++] = a[i++];
39 
40     while (j <= r)q[k++] = a[j++];
41 
42     for (int i = l, j = 0; i <= r && j < k; i++, j++)
43     {
44         a[i] = q[j];
45     }
46 }
47 
48 int main()
49 {
50     cin >> n;
51 
52     for (int i = 1; i <= n; i++)cin >> a[i];
53 
54     int l = 1, r = n;
55 
56     merge_sort(l, r);
57 
58     cout << ans << endl;
59 
60     return 0;
61 }