https://www.luogu.com.cn/problem/P1908
归并排序是用来求逆序对的
归并排序的思想就是分治
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 5e5 + 10; int n,a[maxn],c[maxn]; int ans; void msort(int l,int r){ if(l == r) return ; int i = l,mid = (l + r) / 2,j = mid + 1; msort(l,mid);msort(mid + 1,r); int k = l; while(i <= mid && j <= r){ if(a[i] <= a[j]) c[k++] = a[i++]; else{ c[k++] = a[j++]; ans += mid - i + 1; } } while(i <= mid) c[k++] = a[i++]; while(j <= r) c[k++] = a[j++]; for(int z = l; z <= r;z++) a[z] = c[z]; } signed main(){ //freopen("in","r",stdin); ios::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; msort(1,n); cout << ans; return 0; }