问题 C: 求逆序对

题目描述

给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。

注意：n<=105，ai<=105

输入

第一行为n,表示序列长度。

接下来的n行，第i+1行表示序列中的第i个数。

输出

所有逆序对总数。

样例输入

4
3
2
3
2

样例输出

3

问题分析

直观方法:

最直接的方法是使用两层循环遍历所有元素对，检查是否构成逆序对。但这种方法的时间复杂度为O(n2)，对于大数据量来说效率较低。

高效算法:

归并排序提供了一种更有效的方式来计算逆序对。

在归并排序的过程中，当一个元素从右半部分移动到左半部分时，它与左半部分所有剩余元素构成逆序对。

这样可以在O(nlogn) 的时间复杂度内计算出逆序对的总数。

分治策略:

使用分治方法将序列分成更小的子序列，分别计算每个子序列的逆序对，然后合并结果。

在合并两个已排序的子序列时，可以计算跨越两个子序列的逆序对。

#include <bits/stdc++.h>
#define int long long // 使用长整型
using namespace std;

// 定义一个函数 merge，用于合并两个子数组并计算逆序对
int merge(vector<int>& a, int l, int mid, int r) {
    vector<int> temp(r - l + 1); // 创建一个临时数组存储合并后的结果
    int i = l, j = mid + 1, k = 0, count = 0; // 初始化指针和计数器

    // 合并两个子数组
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            // 如果左侧元素小于等于右侧元素，复制左侧元素
            temp[k++] = a[i++];
        } else {
            // 如果左侧元素大于右侧元素，复制右侧元素
            // 并增加逆序对的数量（左侧剩余的元素个数）
            temp[k++] = a[j++];
            count = count + (mid - i + 1);
        }
    }
    // 复制剩余的左侧元素
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    // 复制剩余的右侧元素
    while (j <= r) {
        temp[k++] = a[j++];
    }
    // 将合并后的数组复制回原数组
    for (int i = l, k = 0; i <= r; i++, k++) {
        a[i] = temp[k];
    }
    return count; // 返回计数的逆序对数量
}

// 定义一个函数 mS（mergeSort 的缩写），用于递归地分治和合并
int mS(vector<int>& a, int l, int r) {
    int count = 0; // 初始化逆序对计数器
    if (l < r) {
        int mid = (l + r) / 2; // 计算中点
        // 递归地对左右子数组进行排序，并计算逆序对
        count = count + mS(a, l, mid);
        count = count + mS(a, mid + 1, r);
        // 合并两个子数组，并计算逆序对
        count = count + merge(a, l, mid, r);
    }
    return count; // 返回逆序对总数
}

signed main() {
    int n;
    cin >> n; // 读取序列长度
    vector<int> a(n); // 创建序列数组
    for (int i = 0; i < n; i++) {
        cin >> a[i]; // 读取序列元素
    }
    int vi = mS(a, 0, n - 1); // 调用 mS 函数计算逆序对
    cout << vi << endl; // 输出逆序对的数量
}