归并排序求逆序数;
#include#define MAXN 5000+10#define LL long long#include using namespace std;int a[MAXN], tmp[MAXN]; int b[MAXN];LL ans;void Merge(int l, int m, int r){ int i=l; int j=m+1; int k=l; while(i<=m && j<=r) { if(a[i]> a[j]) { tmp[k++]=a[j++]; ans+=m-i+1; } else { tmp[k++]=a[i++]; } } while(i<=m) tmp[k++]=a[i++]; while(j<=r) tmp[k++]=a[j++]; for(int i=l; i<=r; i++) { a[i]=tmp[i]; }}void Merge_sort(int l, int r){ if(l > 1; Merge_sort(l, m); Merge_sort(m+1, r); Merge(l, m, r); }}int main(){ int n; LL res; while(scanf("%d", &n) != EOF) { for(int i=0; i