分治归并排序算法实战：从基础到逆序对统计

2. 进阶应用：交易逆序对的总数

当我们需要统计数组中的逆序对数量时，暴力枚举需要 O(n²)，而利用归并排序的特性，可以在排序的同时完成计数，时间复杂度降为 O(n log n)。

核心思路

在归并的两个有序子数组 [left, mid] 和 [mid+1, right] 进行比较时，如果左边的元素 record[cur1] 大于右边的元素 record[cur2]，那么由于左边部分也是有序的，cur1 及其后面的所有元素都大于 record[cur2]。因此，可以直接累加 mid - cur1 + 1 个逆序对。

代码实现

class Solution {
    vector<int> tmp;
public:
    int reversePairs(vector<int>& record) {
        tmp.resize(50010); // 根据题目数据范围调整
        return mergeSort(record, 0, record.size() - 1);
    }

    int mergeSort(vector<int>& record, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int ret = 0;
        int mid = left + ((right - left) >> 1);
        ret += mergeSort(record, left, mid);
        ret += mergeSort(record, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (record[cur1] <= record[cur2]) {
                tmp[i++] = record[cur1++];
            } else {
                ret += mid - cur1 + 1;
                tmp[i++] = record[cur2++];
            }
        }
        while (cur1 <= mid) {
            tmp[i++] = record[cur1++];
        }
        while (cur2 <= right) {
            tmp[i++] = record[cur2++];
        }
        for (int j = 0; j < right - left + 1; ++j) {
            record[j + left] = tmp[j];
        }
        return ret;
    }
};

3. 计算右侧小于当前元素的个数

这道题要求返回每个索引对应的右侧比它小的数字个数。难点在于归并排序会打乱原始顺序，导致无法直接对应回原索引。

解决方案

我们需要额外创建一个索引数组 index，与数值数组 nums 同步移动。这样在归并排序过程中，即使数值被交换，我们也能通过 index 数组知道该数值原本属于哪个位置，从而更新结果数组 ret。

代码实现

class Solution {
    vector<int> ret;
    vector<int> index;
    int tmpNums[500010];
    int tmpIndex[500010];

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n, 0);
        index.resize(n);
        for (int i = 0; i < n; ++i) {
            index[i] = i;
        }
        mergeSort(nums, 0, n - 1);
        return ret;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            } else {
                // 左侧元素大于右侧元素，说明左侧剩余元素都比右侧当前元素大
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }
        }
        while (cur1 <= mid) {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while (cur2 <= right) {
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }
        for (int j = 0; j < right - left + 1; ++j) {
            nums[j + left] = tmpNums[j];
            index[j + left] = tmpIndex[j];
        }
    }
};

4. 翻转对

翻转对定义为 i < j 且 nums[i] > 2 * nums[j]。这题同样可以利用归并排序解决，但需要注意计算时机和溢出问题。

注意事项

1. 计算时机：必须在排序前或排序过程中计算符合条件的对数。如果在完全排序后再算，相对位置关系可能会丢失。
2. 溢出保护：比较 nums[i] > 2 * nums[j] 时，需将数值转换为 long long 防止乘法溢出。
3. 双指针优化：在归并前的预处理阶段，可以使用双指针快速统计满足条件的对数，然后再执行标准的归并操作。

代码实现

class Solution {
    vector<int> tmp;
    int ret = 0;

public:
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return ret;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 统计翻转对
        int cur1 = left, cur2 = mid + 1;
        while (cur2 <= right) {
            while (cur1 <= mid && (long long)nums[cur1] <= 2LL * (long long)nums[cur2]) {
                cur1++;
            }
            if (cur1 > mid) {
                break;
            }
            ret += mid - cur1 + 1;
            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 j = 0; j < right - left + 1; ++j) {
            nums[j + left] = tmp[j];
        }
    }
};

通过以上几个案例可以看出，归并排序不仅仅是用来排序的工具，其'分治 + 有序合并'的特性使其成为处理区间计数问题的利器。掌握这一模式，能帮你高效解决大量涉及逆序、大小关系的算法题。