本题没有什么难度，一个模板题。之所以要写这个题解，是因为我自己第一次提交的时候，竟然没有 AC。老子立马懵逼了。后面耐心的分析了一下数据，才发现自己的错误在哪里。透剧一下，掉到数据越界的深坑了。所以记录一下。

题目
题目链接
一本通OJ：http://ybt.ssoier.cn:8088/problem_show.php?pid=1311。

OJ：http://47.110.135.197/problem.php?id=4134。

 

分析
一个标准求逆序对模板题。

逆序对
设 A 为一个有 n 个数字的有序集（n > 1），其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。

例如，数组（3，1，4，5，2）的逆序对有(3, 1)，(3, 2)，(4, 2)，(5, 2)，共 4 个逆序对。

算法思路
求数组的逆序对就是对数组进行排序，在排序过程中记录逆序的数量即可。这样我们需要使用稳定算法>排序算法，比如冒泡排序、插入排序和归并排序。

数据范围分析
1、从题目中，我们可以知道 n 的范围是 [1, 10^5]，这样我们就知道所有 O(n^2) 复杂度的算法>排序算法肯定是 TLE，也就是说冒泡排序和插入排序不能使用，只有是要归并排序。

2、假设最坏的情况，也就是这 10^5 个数据全部是倒序，那么逆序对应该是 。

这个数据什么意思？我们来回忆一下 C++ 数据类型 unsigned int 的最大范围是 4,294,967,295，也就是 ，说明 unsigned int 已经容纳不下这个数据。太太太坑爹了。

归并排序求逆序对
这个部分是分析的核心。首先我们用一个样例数据来说明，使用归并排序。假设我们有一个数列 [5 4 2 6 3 1]，使用归并排序来看一下有几个逆序对。

第一步：二分，如下图所示。逆序对数量 = 0。

第二步：第四层 5 和 4 合并：i=l=1; r=2; mid=(l+r)/2=1; j=mid+1=2; 因为 5>4，逆序对数量+mid-i+1=1。b数组：[4 5 0 0 0 0]，j+1>r；退出；a 数组 [4 5 2 6 3 1]。如下图所示。

第三步：第四层 6 和 3 合并：i=l=4; r=5; mid=(l+r)/2=4; j=mid+1=5; 因为 6>3，逆序对数量+mid-i+1=2。b数组：[4 5 0 3 6 0]，j+1>r；退出；a 数组 [4 5 2 6 3 1]。如下图所示。

第四步：第三层 4,5 和 2 合并：i=l=1; r=3; mid=(l+r)/2=2; j=mid+1=3; 因为 4>2，逆序对数量+mid-i+1=4。b数组：[2 4 5 3 6 0]，j+1>r；退出；a 数组 [2 4 5 3 6 1]。如下图所示。

第五步：第三层 3,6 和 1 合并：i=l=4; r=6; mid=(l+r)/2=5; j=mid+1=6; 因为 3>1，逆序对数量+mid-i+1=6。b数组：[2 4 5 1 3 6]，j+1>r；退出；a 数组 [2 4 5 1 3 6]。如下图所示。

第六步：第二层 2,4,5 和 1,3,6 合并：i=l=1; r=6; mid=(l+r)/2=3; j=mid+1=4; 因为 2>1，逆序对数量+mid-i+1=9。b数组：[1 2 4 5 3 6]，j+1；对应 2<3，b数组：[1 2 4 5 3 6]，i+1；对应 4>3，逆序对数量+mid-i+1=11，b数组：[1 2 3 4 5 6]。j+1；对应 4<6，b数组：[1 2 3 4 5 6]；i+1，5<6，b数组：[1 2 3 4 5 6]；i+1>mid，退出，a 数组 [1 2 3 4 5 6]，有序。如下图所示。

从上面的分析可以看出，使用归并排序求逆序对，最核心的是下面这句话

ans+=mid-i+1;

//http://ybt.ssoier.cn:8088/problem_show.php?pid=1311
//求逆序对
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e6+4;
int nums[MAXN] = {};
int tmps[MAXN];
long long ans = 0;
 
//使用归并排序
void merge(int l, int mid, int r) {
    int i=l;
    int j=mid+1;
    int k=l;
    while (i<=mid && j<=r) {
        if (nums[i]>nums[j]) {
            tmps[k++]=nums[j++];
            ans+=mid-i+1;
        } else {
            tmps[k++]=nums[i++];
        }
    }
 
    while (i<=mid) {
        tmps[k++]=nums[i++];
    }
    while (j<=r) {
        tmps[k++]=nums[j++];
    }
    for (i=l; i<=r; i++) {
        nums[i]=tmps[i];
    }
}
 
void mergeSort(int l, int r) {
    int mid;
    if (l < r) {
        mid = l+((r-l)>>1);
        mergeSort(l, mid);
        mergeSort(mid+1, r);
        merge(l, mid, r);
    }
}
 
int main() {
    int n;
    cin >> n;
    int i;
    for (i=0; i<n; i++) {
        cin >> nums[i];
    }
 
    mergeSort(0, n-1);
 
    cout << ans << endl;
 
    return 0;
}

————————————————
版权声明：本文为CSDN博主「努力的老周」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/justidle/article/details/104565227