题目描述
给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000
输入样例
6
2 3 4 5 6 1
输出样例
5
算法
归并应用
分三种情况，1逆序对在数轴的左边，2逆序对在数轴的右边，3逆序对跨数轴左右。
写的时候注意 res += mid - i + 1; 这里跟之前找第K个数不一样，这里是 mid - i 。
还有就是 if(q[i] <= q[j]) tmp[k++] = q[i++]; 这里和之前归并排序不一样。
这里是先判断 (q[i] <= q[j] ，表示当前的q[i]和q[j]不是逆序对。不是的话res就不用累加。
时间复杂度
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int q[N], tmp[N];
LL merge_sort(int l, int r){
if(l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k++] = q[i++];
else{
res += mid - i + 1;
tmp[k++] = q[j++];
}
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
return res;
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) scanf("%d", &q[i]);
cout << merge_sort(0, n - 1) << endl;
return 0;
}
我想问一下为什么是 mid - i + 1呢 ？
这里是将左右两个已经排好序的数组，合并成一个新的有序数组tmp。
同时遍历这两个数组，数小的先放进去，当在左边数组发现一个数比右边数组大的时候，(q[i] > q[j])， 就说明发现了逆序对的第三种情况（逆序对跨数轴左右），这个时候，q[i] ~ q[mid] ，一共 mid - i + 1 个数都是比 q[j] 大的（因为左右两边的数组都已经排好序了），也就是找到了右边数组上关于q[j]有mid - i + 1个逆序对，res要+=mid - i + 1.右边数组上关于每个数的逆序对数之和，就是当前合并的区间里，逆序对跨数轴左右情况的总逆序对数。
明白了，谢谢~
这里是以q[j]来看的，能否以q[i]来看呢，q[mid+1]到q[j]都比我q[i]小，res+=j-mid，我尝试了这样答案就不对了
因为i和j所在的左右两个区间，在合并前已经是非递减的了，合并的时候如果遇到了q[i] < q[j] 的情况，只能说明区间范围[mid + 1, j] 里的数确实小于 q[i]这个数，但是关于左边q[i]的逆序对总数，是在区间范围[mid + 1, r]找的，如果j后面的存在数满足大于q[j]也小于q[i], 那合并的时候只res+=j-mid, 就少加了 。
比如合并 4 5 6 ，1 2 3 的时候， res = 3 + 3 + 3(1 2 3 先依次进入新数组)， 但如果是以q[i]来看的话，那就算成了 res = 1 + 2 + 3
用你给的样例模拟了一遍清楚多了，感觉是因为非递减这个性质以及我们从小到大遍历的这个顺序导致用q[i]为比较标准会少算，而用q[j]就不会少算，非常感谢！
嗯嗯
大佬大佬，想了半个小时始终数据不对，结果是res = merge_sort(l, mid) + merge_sort(mid + 1, r)这个部分没理解，这个是递归到最小段是吧
嗯对，先递归左边到单个数，单个数没有逆序对，返回0，然后再返回到两个数，计算完结果后排序，返回上一次递归的地方。
q数组左边递归完了，再递归q数组右边，步骤和左边一样，然后再最后一次计算和排序就完事了。
每次递归都是先左后右，mid计算完每次都算左边的。
大佬你好，我想问一下为什么说这样就可以自动算出来这两部分逆序对的数量而不用任何像第三种情况那样的公式进行计算呢？
#include [HTML_REMOVED]
using namespace std;
const int N=100010;
int a[N],tmp[N];
int n;
long long ans=0;
void mergesort(int a[],int l,int r)
{
if(l>=r) return;
int k=0,i=l,mid=(l+r)/2,j=mid+1;
mergesort(a,l,mid);
mergesort(a,mid+1,r);
while(i<=mid && j<=r)
{
if(a[i]<a[j]) tmp[k]=a[i];
else
{
ans = ans + (mid-i+1);
tmp[k]=a[j];
}
}
while(i<=mid) tmp[k]=a[i];
while(j<=r) tmp[k]=a[j];
for(j=0,i=l;i<=r;j,i) a[i]=tmp[j];
}
int main()
{
scanf(“%d”,&n);
for(int i=0;i<n;i++) scanf(“%d”,&a[i]);
mergesort(a,0,n-1);
cout<<ans;
return 0;
}
这哪里不对
想问下res = merge_sort(l, mid) + merge_sort(mid + 1, r); 是什么意思啊
逆序对的数量 从三个方面找，左边逆序对，右边逆序对，还有逆序对跨左右两边。这一步就是先把前两种情况的逆序对数量加了起来，后面的代码是在和合并左右两段的数值(已排好序)中，找逆序对跨左右两边的情况。就是利用归并的过程，计算了一下三种逆序对情况的数量总和。