题解

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

//归并排序+逆序对查找
#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(nlogn)
额外的空间复杂度：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)
*/

树状数组：

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1048576;
int n,a[N],c[N],lns[N],len,ans;
int lowbit(int n){
	return n&(-n);
}
int get(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i))res+=c[i];
	return res;
}
void add(int x,int ind){
	for(int i=x;i<N;i+=lowbit(i))c[i]+=ind;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		lns[i]=a[i];
	}
	sort(lns+1,lns+n+1);//快排O(nlogn)
	len=unique(lns+1,lns+n+1)-lns-1;//找离散化之后的长度
	for(int i=1;i<=n;i++)a[i]=lower_bound(lns+1,lns+len+1,a[i])-lns;//离散化
	//离散化完成，接下来装桶，前缀和（树状数组优化）来求多少逆序对已有
	for(int i=1;i<=n;i++){
		add(a[i],1);//装桶
		ans+=get(n)-get(a[i]);//统计逆序对
	}
	cout<<ans;
	return 0;
}
/*
时间复杂度：O(nlogn)
额外的空间复杂度：O(n)离散化用，O(n)树状数组用作桶+前缀和
*/