1.归并排序方法求逆对
(方法相同于P1908 逆序对)
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;
int a[N], st[N];
long long ans = 0;
void merge_sort(int l, int r){
if(l == r) return;
int mid = (l + r) >> 1;
int i = l, j = mid + 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int t = 1;
while(i <= mid && j <= r)
if(a[j] < a[i])
ans += mid - i + 1, st[t ++] = a[j ++];
else
st[t ++] = a[i ++];
while(i <= mid) st[t ++] = a[i ++];
while(j <= r) st[t ++] = a[j ++];
for(i = l, j = 1; i <= r; i ++, j ++) a[i] = st[j];
return;
}
int main(){
int n;
scanf("%d", &n);
for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
merge_sort(1, n);
printf("%lld", ans);
return 0;
}