1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
#include <iostream>
#include <vector>
using namespace std;
int all_together_now(vector<int>& v, int e, int m, int d) {
vector<int> aux(d-e+1);
int count = 0;
int o = m-e;
int i = e;
int j = m+1;
int k = 0;
while(i<=m and j<=d) {
if (v[i] > v[j]) {
aux[k] = v[j]; ++k; ++j;
count += o-i;
}
else {aux[k] = v[i]; ++k; ++i;}
}
while (i<=m) {aux[k] = v[i]; ++k; ++i; }
while (j<=d) {aux[k] = v[j]; ++k; ++j; }
for (int p = 0; p < d-e+1; ++p) v[e+p] = aux[p];
return count;
}
int no_inv(vector<int>& v, int e, int d) {
if (e < d) {
int m = (e+d)/2;
return no_inv(v, e, m) + no_inv(v, m+1, d) + all_together_now(v, e, m, d);
}
return 0;
}
int main () {
int n;
while (cin >> n) {
vector<int> V(n);
for (int i = 0; i < n; ++i) cin >> V[i];
cout << no_inv(V, 0, V.size()-1) << endl;
}
}
|