思路

可以顺便把这道一模一样的题给A掉Luogu P5463 小鱼比可爱（加强版）
各位可以做完《逆序数》再过来，我是用归并排序写的。
考虑到对于一个逆序对<i,j>，i∈[l,m],j∈[m+1,r]，那么它是所有区间[x,y]，x∈[l,i]，y∈[j,r]中的逆序对，
每一次merge计算逆序对的时候都乘以外面的区间数（L*(n-R+1)），就是那些逆序对的总贡献。
###代码

#include<bits/stdc++.h>
#define int __int128
using namespace std;
typedef long long ll;
const int maxn=1e6+5;

struct X{
    int id,val;
}a[maxn],tmp[maxn];

int n,ans=0,sum=0;

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

void merge(int l,int m,int r){
    int i=l,j=m+1,k=l;
    ll sum=0;
    for(int i=l;i<=m;i++){
        sum+=a[i].id;
    }
    while(i<=m&&j<=r){
        if(a[i].val>a[j].val){
            ans+=sum*(n-a[j].id+1);
            tmp[k++]=a[j++];
        }else{
            sum-=a[i].id;
            tmp[k++]=a[i++];
        }
    }
    while(i<=m) tmp[k++]=a[i++];
    while(j<=r) tmp[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=tmp[i];
}

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);
    merge(l,mid,r);
}

signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].val);
        a[i].id=i;
    }
    merge_sort(1,n);
    write(ans);
    return 0;
}