翻转对

来源

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

class Solution {
 private:
  int process(vector<int>& arr, int l, int r) {
    if (l == r) return 0;
    int mid = l + ((r - l) >> 1);
    return process(arr, l, mid) + process(arr, mid + 1, r) +
           merge(arr, l, mid, r);
  }

  int merge(vector<int>& arr, int l, int mid, int r) {
    int ans = 0, windowR = mid + 1;
    for (int i = l; i <= mid; i++) {
      while (windowR <= r && (long)arr[i] > (long)arr[windowR] * 2) windowR++;
      ans += windowR - mid - 1;
    }
    vector<int> help(r - l + 1, 0);
    int i = 0, p1 = l, p2 = mid + 1;

    while (p1 <= mid && p2 <= r) {
      help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid) help[i++] = arr[p1++];
    while (p2 <= r) help[i++] = arr[p2++];
    for (i = 0; i < help.size(); i++) arr[l + i] = help[i];
    return ans;
  }

 public:
  int reverse_pairs(vector<int>& arr) {
    if (arr.size() < 2) return 0;
    return process(arr, 0, arr.size() - 1);
  }
}