给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000
数列中的元素的取值范围 [1,109]
输入样例：
6
2 3 4 5 6 1
输出样例：
5
这段代码使用归并排序算法对输入的数组进行排序，并输出排序后的数组。在 merge_sort 函数中，通过递归调用将数组不断分割成更小的部分，然后将这些部分进行合并排序。在合并排序的过程中，通过比较左半部分和右半部分的元素大小，将较小的元素放入临时数组。最后，将临时数组中的元素复制回原数组，完成排序。最后在 main 函数中，输入数组并调用 merge_sort 函数进行排序，然后输出排序后的数组。
#include<iostream>
using namespace std;
const int N =1e5 + 7;
int n,q[N],tmp[N];
void merge_sort(int l,int r){
if(l>=r) return ;
int mid=l+r>>1;
merge_sort(l,mid); // 递归调用左半部分
merge_sort(mid+1,r); // 递归调用右半部分
int i=l,j=mid+1;
int k=1;
while(i<=mid && j<=r){
if(q[i]<=q[j]) tmp[k++]=q[i++]; // 左半部分的元素小于等于右半部分的元素，将左半部分的元素放入临时数组
else {
tmp[k++]=q[j++]; // 右半部分的元素小于左半部分的元素，将右半部分的元素放入临时数组
}
}
while(i<=mid) tmp[k++]=q[i++]; // 处理剩余的左半部分的元素
while(j<=r) tmp[k++]=q[j++]; // 处理剩余的右半部分的元素
for(int i=l,j=1;i<=r;i++,j++)
{
q[i]=tmp[j]; // 将临时数组中的元素复制回原数组
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>q[i];
merge_sort(1,n); // 调用归并排序函数
// 输出排序后的数组
for(int i=1;i<=n;i++) cout<<q[i]<<" ";
cout<<endl;
return 0;
}
这里我们用图更能说明问题
观察上述这幅图，我们将数组一分为 2 ，并且左边的数组 和 右边的数组都是排好序的【正序】
那么我们再看
可能到这里会有小伙伴怀疑这样做会导致答案的重复，那么我们就再用一张图解释归并的本质
刚才我们举例的区间可成看出相邻的 区间 1 号，区间 2 号。
#include<iostream>
using namespace std;
const int N =1e5 + 7;
int n,q[N],tmp[N];
long long res;
void merge_sort(int l,int r){
if(l>=r) return ;
int mid=l+r>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
int i=l,j=mid+1;
int k=1;
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=1;i<=r;i++,j++)
{
q[i]=tmp[j];
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>q[i];
merge_sort(1,n);
cout<<res<<endl;
return 0;
}