归并排序实战：计算右侧小于当前元素个数与翻转对

流程解析

在合并阶段，当 nums[cur1] > nums[cur2] 时，意味着 nums[cur1] 及其左侧剩余的所有元素都比 nums[cur2] 大。由于右半部分已经有序，从 cur2 到 right 的所有元素都小于 nums[cur1]，数量为 right - cur2 + 1。通过 index 数组，我们可以准确地将这个计数累加到原数组对应位置的 counts 中。

50. 翻转对

题目描述

给定一个数组 nums，如果 i < j 且 nums[i] > 2 * nums[j]，则称 (i, j) 为一个翻转对。返回数组中翻转对的总数。

核心思路

翻转对和逆序对的定义大同小异，只是条件变成了 nums[i] > 2 * nums[j]。我们依然可以使用归并排序的思想，将问题分解为三部分：左半区间翻转对的数量、右半区间翻转对的数量、一左一右选择时翻转对的数量。

关键区别在于：上一道题可以在合并的同时计算，但这道题要求的是左边元素大于右边元素的两倍。如果在合并过程中直接操作，可能会破坏顺序导致无法快速判断。因此，我们需要先统计满足条件的翻转对数量，再进行归并排序。

实现代码

class Solution {
public:
    vector<int> tmp;
    int count = 0;

    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        mergesort(nums, 0, nums.size() - 1);
        return count;
    }

    void mergesort(vector<int>& nums, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (right - left) / 2 + left;
        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);
        
        // 先统计翻转对数量
        int cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right) {
            // 当左边大于右边的两倍才会进行求值
            if((long long)nums[cur1] > 2LL * nums[cur2]) {
                count += right - cur2 + 1;
                cur1++;
            } else {
                cur2++;
            }
        }
        
        // 再执行标准的归并排序合并
        cur1 = left;
        cur2 = mid + 1;
        int i = 0;
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur1] > nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                tmp[i++] = nums[cur2++];
            }
        }
        while(cur1 <= mid) {
            tmp[i++] = nums[cur1++];
        }
        while(cur2 <= right) {
            tmp[i++] = nums[cur2++];
        }
        
        for(int i = left; i <= right; i++) {
            nums[i] = tmp[i - left];
        }
    }
};

流程解析

这里需要注意类型转换，使用 long long 防止乘法溢出。统计阶段利用了两个子数组分别有序的特性：对于左边的每一个 cur1，找到第一个满足 nums[cur1] <= 2 * nums[cur2] 的 cur2，那么 cur2 之后的所有元素都满足翻转对条件。统计完成后，再像普通归并排序一样合并数组，保证上一层递归能继续处理。

总结

这两道题展示了归并排序在统计类问题中的强大能力。49 题通过维护原始索引解决了动态位置下的计数问题；50 题则通过分离'统计'与'合并'步骤，巧妙处理了非单调的比较条件。掌握这种分治策略，面对类似的逆序对变种问题时就能游刃有余。