803
逆序對
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100010], t[100010];
long long ans = 0;
void merge_sort(int* a, int x, int y, int* t){
if (y - x > 1){
int m = x + (y - x) / 2;
int p = x, q = m, i = x;
merge_sort(a, x, m, t);
merge_sort(a, m, y, t);
while (p < m || q < y)
if (q >= y || (p < m && a[p] < a[q])) t[i++] = a[p++];
else t[i++] = a[q++], ans += m - p;
for (int j = x; j < y; j++) a[j] = t[j];
}
}
int main(){
int n; cin>>n;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
merge_sort(a, 0, n, t);
cout<<ans;
return 0;
}最後更新：2017-08-13 22:33:43