归并排序求逆序对

逆序对的求法

树状数组

不多讲，代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,c[40005]={0},a[40005]={0},b[40005]={0};  //定义数组，b[]为读入的数组，a[]为要离散化后的数组，C[]为树状数组
inline void Add(register int x)  //树状数组加入
{
    for(;x<=n;x+=(x&-x))
        c[x]++;  //因为这里只需要1，所以我就写出c[x]++了
}
inline int Sum(register int x)  //树状数组求和，同上面的sum(x)
{
    register int s=0;  //计数的变量
    for(;x>0;x-=(x&-x))  //累计
        s+=c[x];
    return s;  //返回结果
}
bool cmp1(const int &x,const int &y)  //离散化需要用的，上面有讲
{
    return b[x]>b[y];
}
int main()
{
    int ans=0;  //ans为最后的结果
    scanf("%d",&n);  //读入n
    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);  //读入
        a[i]=i;  //顺便初始化一下a数组
    }
    sort(a+1,a+n+1,cmp1);  //给a数组排序，达到最终的效果
    for(register int i=1;i<=n;i++)
    {
        Add(a[i]);  //依次加入树状数组
        ans+=Sum(a[i]-1);  //计算结果并累计
    }
    printf("%d",ans);  //输出ans
    return 0;  //返回
}

归并排序做法

归并排序求逆序对恰好利用了归并排序的原理，类似二分分治，个人感觉比树状数组好用。
代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+7;
int a[maxn],r[maxn],n;
long long ans=0;
void msort(int s,int t){ //归并排序
    if(s==t) return;
    
    int mid=s+t>>1;
    msort(s,mid);
	msort(mid+1,t);
	
    int i=s,j=mid+1,k=s;
    while(i<=mid && j<=t)
    {
    	if(a[i]<=a[j]) r[k++]=a[i++];
    	else
    	{
    		r[k++]=a[j++];
			ans+=(long long)mid-i+1; //记录逆序对
    	}
    }
    while(i<=mid) r[k] = a[i],k++,i++;
    while(j<=t) r[k] = a[j],k++,j++;
    for(int i=s;i<=t;i++) a[i]=r[i];
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    msort(1,n);
    printf("%lld\n",ans);
    return 0;
}