思路

在降序归并排序里求解

如果监测到逆序对的话就ans+=mid+1-i;

为什么不是逆序对位置的差?

因为每次求解完两边的序列都是有序的,而它们的贡献在前一次递归中已经被计算了!

code

#include <bits/stdc++.h>

#define int long long

using namespace std;

int ans= 0;

const int N = 3e5 + 10;

int a[N],b[N];

void merge(int l,int r) {
    if(l == r) {
        return;
    }
    int mid = (l + r) / 2;
    merge(l,mid);
    merge(mid+1,r);
    int i = l,j = mid+1;
    int now = l;
    while(i <= mid && j <= r) {
        if(a[i] >= a[j]) {
            b[now++] = a[i];
            i++;
        }else {
            ans += mid + 1 - i;
            b[now++] = a[j];
            j++;
        }
    }
    while(i <= mid) b[now++] = a[i++];

    while(j <= r) b[now++] = a[j++];

    for(int i = l;i <= r;i++) a[i] = b[i];
}

signed main() {
    int n;
    cin>>n;
    for(int i = 1;i <= n;i++) {
        cin>>a[i];
    }
    merge(1,n);
    cout<<ans;
    return 0;
}