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
| #include <vector> using namespace std; struct Seg { int mi, ma, count; Seg *l, *r;
Seg(vector<int> A, int left, int right) : count(0), l(nullptr), r(nullptr) { mi = A[left], ma = A[right]; if (left == right) return; int m = (left + right) / 2; l = new Seg(A, left, m); r = new Seg(A, m + 1, right); }
~Seg() { if(l) delete l; if(r) delete r; }
int query(int s, int e) { if (mi > e or ma < s) return 0; if (s <= mi and ma <= e) return count; return (l ? l->query(s, e) : 0) + (r ? r->query(s, e) : 0); }
void update(int n, int v) { if (mi <= n and n <= ma) { count++; if (l) l->update(n, v); if (r) r->update(n, v); } } };
int countInversions(vector<int> array) { if(array.empty()) return 0; int res = 0, n = array.size(); vector<int> sorted = array;
sort(begin(sorted), end(sorted)); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
Seg *seg = new Seg(sorted, 0, sorted.size() - 1); for (int i = 0; i < n; i++) { int s = array[i] + 1, e = sorted.back(); if (s <= e) res += seg->query(s, e); seg->update(array[i], 1); }
delete seg; return res; }
|