算法分析

首先，暴力法会超时，因此需要一定的优化，这里把它放在归并排序处，实际上就借鉴了归并排序的思想，归并排序在进行区间合并，进行赋值给临时数组的时候，左右两个区间分别为[l, mid]，[mid+1, r] ，对于a[i] 和 a[j] ，一定满足如下的情况: a[l~i]<=a[j] ，a[mid+1 ~ r] >=a[j] ，因此对于 a[j] 来说，存在 mid - i + 1 个数比a[j] 大

核心代码

while (i <= mid && j <= r)
    /*
        逆序对是严格大于，所以<=都会被排除，因此在建立临时数组的过程中
        当 q[i] > q[j] 时，满足 q[l,i-1] 都是比 q[j] 小，q[i,mid] 都是比 q[j] 大，
        所以对于q[j]来说，有 mid-i+1 数比它大，因此满足 <num, q[j]> 的逆序对数有mid-i+1
    */
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
例如[3,4,1,2]中q[0]>q[2],则q[0],q[1]都与q[2]成逆序对,而q[mid]与q[i]有mid-i+1个数字，
因此逆序对增加mid-i+1

完整代码

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, a[N], q[N];

ll merge_sort(int l, int r)
{
    if(l==r) return 0;
    int mid = l+r>>1, k = 0, i = l, j = mid+1;
    ll res = merge_sort(l, mid) + merge_sort(mid+1, r);
    while( i <= mid && j <= r)
    {
        if(a[i] <= a[j]) q[k++] = a[i++];
        else{
            res += mid -i + 1;
            q[k++] = a[j++];
        }
    }
    while(i<=mid) q[k++] = a[i++];
    while(j<=r) q[k++] = a[j++];

    for(i = l, j = 0 ;i<=r;i++,j++) a[i] = q[j];

    return res;
}

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