AcWing
788. 逆序对的数量
如果暴力枚举，枚举右端点i，n-1次，枚举左端点j，i-1次，共需要约n^2 / 2次，时间复杂度是5e9，会超时。
如果所处理的区间有序，计算逆序对的数量将会很快。可以考虑使用归并排序的过程，因为在区间归并时，左右两边的区间是有序的，只需使用双指针，就可以在线性时间内求出一轮中(左端点在左区间，右端点在右区间情况的)逆序对的数量。具体地，可以将求区间[1, n]内所有逆序对的数量mergesort(int l, int r)分为下面三个部分：
- 区间
[l(1), mid]内逆序对的数量 - 区间
[mid + 1, r(n)]内逆序对的数量 - 左端点在左区间
[l, mid]，右端点在右区间[mid + 1, r]情况的逆序对的数量
对于前两者，可以递归使用mergesort()求数量，对于最后一部分，使用双指针求数量。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010;
int a[N], tmp[N];
typedef long long LL;
LL mergesort(int l, int r){
if(l >= r) return 0;
int mid = l + r >> 1;
LL res = 0;
res += mergesort(l, mid); // [l, mid]逆序对数量
res += mergesort(mid + 1, r); // [mid + 1, r]逆序对数量
int pl = l, pr = mid + 1;
while(pr <= r){ // i在[l, mid]，j在[mid + 1, r]的逆序对(i, j)数量
while(pl <= mid && a[pl] <= a[pr]) pl++;
res += (mid - pl + 1);
pr++;
}
pl = l, pr = mid + 1;
int pt = 1;
while(pl <= mid && pr <= r){
if(a[pl] <= a[pr]) tmp[pt++] = a[pl++];
else tmp[pt++] = a[pr++];
}
while(pl <= mid) tmp[pt++] = a[pl++];
while(pr <= r) tmp[pt++] = a[pr++];
for(int i = l, j = 1; i <= r; i++, j++) a[i] = tmp[j];
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
LL res = mergesort(1, n);
cout << res;
return 0;
}