逆序对

luckydrawbox · 2021-10-15 17:29:46 · 个人记录

归并排序是求逆序对的常用办法，故这里也使用归并排序。

宏定义

请根据需要更改排序基本类型 NXD\_T。

#define NXD_T long long

上面是以 \text{long long} 为基本类型。

变量

r[i]：辅助变量，因此空间复杂度为 O(n)。

函数

nxd_compare(NXD_T x,NXD_T y)：比较的函数，返回值是 \text{bool} 类型，如 x<y，就是从小到大排序。

nxd(NXD_T *a,int s,int t)：对于 a 数组的 a_s\sim a_t 进行排序，并返回 a_s\sim a_t 的符合要求的逆序对数，如对于上面的比较函数的返回值为 x<y 的情况，求的是 i<j 且 a_i>a_j 的逆序对数。

#define NXD_T long long
NXD_T r[N];
bool nxd_compare(NXD_T x,NXD_T y){
    return x<y;
}
long long nxd(NXD_T *a,int s,int t){
    if(s==t)
        return 0;
    int mid=(s+t)/2;
    int i=s,j=mid+1,k=s;
    long long ans=nxd(a,s,mid)+nxd(a,mid+1,t);
    while(i<=mid&&j<=t)
        if(a[i]<=a[j]){
            r[k++]=a[i++];
            ans+=j-mid-1;
        }
        else
            r[k++]=a[j++];
    while(i<=mid){
        r[k++]=a[i++];
        ans+=j-mid-1;
    }
    while(j<=t)
        r[k++]=a[j++];
    for(int i=s;i<=t;i++)
        a[i]=r[i];
    return ans;
}