昨天刚好做到这题，发现网上题解都讲的不是很详细，于是决定自己手写一篇。
归并排序能统计逆序对的数量
为什么归并排序能统计逆序对数量？？？
归并排序的特点是，以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 }