逆序对

1.题目

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update:数据已加强。

输入格式

第一行，一个数 $n$，表示序列中有 $n$个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

输出格式

输出序列中逆序对的数目。

提示

对于 $25\%$ 的数据，$n \leq 2500$

对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。

对于所有数据，$n \leq 5 \times 10^5$

请使用较快的输入输出

2.分析

题目要求计算一个正整数序列中的逆序对数目。逆序对的定义是：对于序列中的两个元素 (a_i) 和 (a_j)，如果 (a_i > a_j) 且 (i < j)，则称 ((a_i, a_j)) 为一个逆序对。

例如，序列 [5, 4, 2, 6, 3, 1] 中的逆序对有：

• (5, 4)
• (5, 2)
• (5, 3)
• (5, 1)
• (4, 2)
• (4, 3)
• (4, 1)
• (2, 1)
• (6, 3)
• (6, 1)
• (3, 1)

总共有 11 个逆序对。

归并排序讲解

归并排序是一种有效的排序算法，时间复杂度为 (O(n \log n))。它的基本思想是将数组分成两个子数组，分别对这两个子数组进行排序，然后将它们合并成一个有序数组。在合并的过程中，可以顺便统计逆序对的数目。

归并排序步骤

1. 分割：将数组分成两个子数组。
2. 递归排序：对每个子数组进行递归排序。
3. 合并：将两个已排序的子数组合并成一个有序数组，并在合并的过程中统计逆序对。

统计逆序对

在合并两个已排序的子数组时，如果左子数组的当前元素大于右子数组的当前元素，则这些元素构成逆序对。因为左子数组的当前元素大于右子数组的当前元素，且左子数组的当前元素在原数组中的位置在右子数组的当前元素之前。

3.代码

#include <iostream>
#include <vector>

using namespace std;

// 合并两个子数组并计算逆序对
long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    // 创建临时子数组
    vector<int> leftSub(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> rightSub(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left;
    long long invCount = 0;

    // 合并两个子数组并计算逆序对
    while (i < leftSub.size() && j < rightSub.size()) {
        if (leftSub[i] <= rightSub[j]) {
            arr[k++] = leftSub[i++];
        } else {
            arr[k++] = rightSub[j++];
            // 计算逆序对数量
            invCount += (mid + 1) - (left + i);
        }
    }

    // 复制剩余的元素
    while (i < leftSub.size()) {
        arr[k++] = leftSub[i++];
    }

    while (j < rightSub.size()) {
        arr[k++] = rightSub[j++];
    }

    return invCount;
}

// 使用分治法计算逆序对
long long countInversions(vector<int>& arr, int left, int right) {
    long long invCount = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 递归计算左半部分的逆序对
        invCount += countInversions(arr, left, mid);
        // 递归计算右半部分的逆序对
        invCount += countInversions(arr, mid + 1, right);
        // 合并并计算跨越两半的逆序对
        invCount += mergeAndCount(arr, left, mid, right);
    }
    return invCount;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    cout << countInversions(arr, 0, n - 1) << endl;

    return 0;
}

def count_inversions(data):
    """ 
    求逆序对函数： 
    使用分治法，基于归并排序的思想
    逆序对分为三类：
    1. 两个元素都在左半部分
    2. 两个元素都在右半部分  
    3. 一个元素在左半部分，一个元素在右半部分
    """
    if len(data) <= 1:
        return data, 0
    
    mid = len(data) // 2
    left = data[:mid]
    right = data[mid:]

    # 递归处理左右两部分
    left_sorted, left_inversions = count_inversions(left)
    right_sorted, right_inversions = count_inversions(right)
    
    # 合并并计算跨越左右两部分的逆序对
    merged, split_inversions = merge_and_count(left_sorted, right_sorted)
    
    # 总逆序对数 = 左半部分逆序对 + 右半部分逆序对 + 跨越两部分的逆序对
    total_inversions = left_inversions + right_inversions + split_inversions
    
    return merged, total_inversions


def merge_and_count(left, right):
    """ 
    合并两个已排序的数组，并计算跨越两部分的逆序对数量
    """
    result = []
    inversions = 0
    i = j = 0
    
    # 合并过程中统计逆序对
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            # 当 left[i] > right[j] 时，left[i] 及其后面的所有元素都大于 right[j]
            # 因此产生 len(left) - i 个逆序对
            inversions += len(left) - i
            j += 1
    
    # 添加剩余元素
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result, inversions


# 测试代码
data = [5, 4, 2, 6, 3, 1]
print("原始数据为：", data)
print("-------------------------------")

sorted_data, inversion_count = count_inversions(data)
print("排序之后的数据为：", sorted_data)
print("逆序对数量为：", inversion_count)
print("-------------------------------")