题解

两个版本
归并排序【经典算法】：

//归并排序+逆序对查找
#include<iostream>
using namespace std;
const int N=5e5;
int n,s[N],a[N],b[N];
long long res;
void msort(int l,int r){
    //归
    if(l>=r)return;
    int mid=(l+r)/2;//二分 归
    msort(l,mid);
    msort(mid+1,r);
    //并
    int i,j,k;
    for(i=l;i<=mid;i++)a[i]=s[i];
    for(j=mid+1;j<=r;j++)b[j]=s[j];
    i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){//边比较边更新
        if(a[i]<b[j]){
            s[k++]=a[i++];
        }else{
            res+=mid-i+1;//逆序对
            s[k++]=b[j++];
        }
    }
    while(i<=mid){//i没有到达mid，若原已到达则不会进入
        s[k++]=a[i++];
    }
    while(j<=r){//j没有到达r，若原已到达则不会进入
        s[k++]=b[j++];
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i];
    msort(0,n-1);
    cout<<res<<endl;
    return 0;
}
/*
排序+查找 时间复杂度：O(nlog2n)
额外的空间复杂度：O(n)
*/

冒泡排序：

//冒泡+逆序对
#include<iostream>
using namespace std;
const int N=5e5+5;
int s[N];
int main(){
    int n,c=0;
    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++)if(s[i]>s[j])c++;
    cout<<c;
    return 0;
}
/*
排序+查找 时间复杂度：O(n^2)
额外的空间复杂度：O(1)
*/