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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <vector>
#include <iostream>
//#include <gtest/gtest.h>
using std::vector;
long mergeInversionCount(vector<int> &B, vector<int> &C, vector<int> &D) {
long count = 0;
while (B.size() != 0 && C.size() != 0) {
int b = B[0];
int c = C[0];
if (b <= c) {
D.push_back(b);
B.erase(B.begin());
} else {
count += B.size();
D.push_back(c);
C.erase(C.begin());
}
}
D.insert(D.end(), B.begin(), B.end());
D.insert(D.end(), C.begin(), C.end());
return count;
}
long getInversionCountFromList(vector<int> &A, vector<int> &D) {
long numberOfInversions = 0;
if (A.size() == 1) {
D.push_back(A[0]);
return 0;
}
int m = A.size() / 2;
vector<int> D1;
vector<int>::const_iterator first = A.begin();
vector<int>::const_iterator last = A.begin() + m;
vector<int> newVec(first, last);
numberOfInversions += getInversionCountFromList(newVec, D1);
vector<int> D2;
vector<int>::const_iterator ffirst = A.begin() + m;
vector<int>::const_iterator llast = A.end();
vector<int> newVecc(ffirst, llast);
numberOfInversions += getInversionCountFromList(newVecc, D2);
long mergeCount = mergeInversionCount(D1, D2, D);
return numberOfInversions + mergeCount;
}
//TEST(InversionCount, test1) {
// vector<int> a = { 2, 3, 9, 2, 2 };
// vector<int> result(5);
// ASSERT_EQ(4, getInversionCountFromList(a, result));
//}
int main() {
int n;
std::cin >> n;
vector<int> a(n);
for (size_t i = 0; i < a.size(); i++) {
std::cin >> a[i];
}
vector<int> b(a.size());
std::cout << getInversionCountFromList(a, b) << '\n';
}
|
