leetcode

0 class SegmentTree {

1 const int n;

2 vector<int> t = vector<int>(2 * n, 1);

3

4 public:

5 SegmentTree(const int n) : n(n) {

6 for (int i = n - 1; i > 0; i--)

7 t[i] = t[i * 2] + t[i * 2 + 1];

8 }

9

10 int sum(int l, int r) const {

11 int res = 0;

12

13 for (l += n, r += n; l < r; l /= 2, r /= 2) {

14 if (l & 1) res += t[l++];

15 if (r & 1) res += t[--r];

16 }

17

18 return res;

19 }

20

21 void update(int p) {

22 for (t[p += n]--; p > 1; p /= 2)

23 t[p / 2] = t[p] + t[p ^ 1];

24 }

25 };

26

27 class Solution {

28 public:

29 int reversePairs(const vector<int> &nums) const {

30 const int n = size(nums);

31

32 // sort the array using index array

33 static int idxs[50001];

34 iota(idxs, idxs + n, 0);

35 sort(idxs, idxs + n, [&](int a, int b) { return nums[a] < nums[b]; });

36

37 static int rev[50001];

38 for (int i = 0; i < n; i++) {

39 rev[idxs[i]] = i;

40 }

41

42 int res = 0;

43 SegmentTree seg(n);

44 for (int i = n - 1; i >= 0; i--) {

45 seg.update(rev[i]);

46 const auto cmp = [&](long long value, int &idx) { return value < nums[idx]; };

47 const auto it = upper_bound(idxs, idxs + n, nums[i] * 2ll, cmp);

48 if (it == idxs + n) continue;

49 res += seg.sum(it - idxs, n);

50 }

51

52 return res;

53 }

54 };