1
class Solution {
2
 public:
3
  int merge_count(vector<int> &nums, int s, int e) {
4
    int i;
5
    int mid = (s + e) / 2;
6
    int j = mid + 1;
7
    long long int count = 0;
8
    for (i = s; i <= mid; i++) {
9
      while ((j <= e) && ((double)nums[i] / 2.0) > nums[j]) {
10
        j++;
11
      }
12
      count += j - (mid + 1);
13
    }
14
    i = s;
15
    j = mid + 1;
16
    vector<int> ans;
17
    while ((i <= mid) && (j <= e)) {
18
      if (nums[i] <= nums[j]) {
19
        ans.push_back(nums[i]);
20
        i++;
21
      } else {
22
        ans.push_back(nums[j]);
23
        j++;
24
      }
25
    }
26
    while (i <= mid) {
27
      ans.push_back(nums[i]);
28
      i++;
29
    }
30
    while (j <= e) {
31
      ans.push_back(nums[j]);
32
      j++;
33
    }
34
    for (int k = s; k <= e; k++) {
35
      nums[k] = ans[k - s];
36
    }
37
    return count;
38
  }
39

40
  int reverse_count(vector<int> &nums, int s, int e) {
41
    if (s >= e) {
42
      return 0;
43
    }
44
    int mid = (s + e) / 2;
45
    int l_count = reverse_count(nums, s, mid);
46
    int r_count = reverse_count(nums, mid + 1, e);
47
    int s_count = merge_count(nums, s, e);
48
    return (l_count + r_count + s_count);
49
  }
50

51
  int reversePairs(vector<int> &nums) {
52
    int res = reverse_count(nums, 0, nums.size() - 1);
53
    return res;
54
  }
55
};