1
class Solution {
2
  int cnt;
3

4
  public int reversePairs(int[] nums) {
5
    int n = nums.length;
6
    cnt = 0;
7
    sort(0, n - 1, nums);
8
    return cnt;
9
  }
10

11
  void sort(int l, int r, int nums[]) {
12
    if (l == r) {
13
      return;
14
    }
15
    int mid = l + (r - l) / 2;
16
    sort(l, mid, nums);
17
    sort(mid + 1, r, nums);
18
    merge(l, mid, r, nums);
19
  }
20

21
  void merge(int l, int mid, int r, int nums[]) {
22
    int n1 = mid - l + 1;
23
    int n2 = r - mid;
24
    int a[] = new int[n1];
25
    int b[] = new int[n2];
26
    for (int i = 0; i < n1; i++) {
27
      a[i] = nums[l + i];
28
    }
29
    for (int j = 0; j < n2; j++) {
30
      b[j] = nums[mid + 1 + j];
31
      int idx = upperBound(a, 0, n1 - 1, 2L * (long) b[j]);
32
      if (idx <= n1) {
33
        cnt += n1 - idx;
34
      }
35
    }
36
    int i = 0;
37
    int j = 0;
38
    int k = l;
39
    while (i < n1 && j < n2) {
40
      if (b[j] <= a[i]) {
41
        nums[k++] = b[j++];
42
      } else {
43
        nums[k++] = a[i++];
44
      }
45
    }
46
    while (i < n1) {
47
      nums[k++] = a[i++];
48
    }
49
    while (j < n2) {
50
      nums[k++] = b[j++];
51
    }
52
  }
53

54
  int upperBound(int a[], int l, int r, long x) {
55
    int ans = r + 1;
56
    while (l <= r) {
57
      int mid = l + (r - l) / 2;
58
      if ((long) a[mid] > x) {
59
        ans = mid;
60
        r = mid - 1;
61
      } else {
62
        l = mid + 1;
63
      }
64
    }
65
    return ans;
66
  }
67
}