0493.cpp (1391B)
1 class SegmentTree { 2 const int n; 3 vector<int> t = vector<int>(2 * n, 1); 4 5 public: 6 SegmentTree(const int n) : n(n) { 7 for (int i = n - 1; i > 0; i--) 8 t[i] = t[i * 2] + t[i * 2 + 1]; 9 } 10 11 int sum(int l, int r) const { 12 int res = 0; 13 14 for (l += n, r += n; l < r; l /= 2, r /= 2) { 15 if (l & 1) res += t[l++]; 16 if (r & 1) res += t[--r]; 17 } 18 19 return res; 20 } 21 22 void update(int p) { 23 for (t[p += n]--; p > 1; p /= 2) 24 t[p / 2] = t[p] + t[p ^ 1]; 25 } 26 }; 27 28 class Solution { 29 public: 30 int reversePairs(const vector<int> &nums) const { 31 const int n = size(nums); 32 33 // sort the array using index array 34 static int idxs[50001]; 35 iota(idxs, idxs + n, 0); 36 sort(idxs, idxs + n, [&](int a, int b) { return nums[a] < nums[b]; }); 37 38 static int rev[50001]; 39 for (int i = 0; i < n; i++) { 40 rev[idxs[i]] = i; 41 } 42 43 int res = 0; 44 SegmentTree seg(n); 45 for (int i = n - 1; i >= 0; i--) { 46 seg.update(rev[i]); 47 const auto cmp = [&](long long value, int &idx) { return value < nums[idx]; }; 48 const auto it = upper_bound(idxs, idxs + n, nums[i] * 2ll, cmp); 49 if (it == idxs + n) continue; 50 res += seg.sum(it - idxs, n); 51 } 52 53 return res; 54 } 55 };