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;
}