求逆序数的三个方法

暴力法

#include<iostream>
#include<algorithm>
using namespace std;
int a[2010];
int main()
{
    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++)
    {
    
        for(int j=i+1;j<=n;j++)
            if(a[i]>a[j]) ans+=1;
    }
    cout<<ans<<endl;
    return 0;
}

归并排序法

#include<iostream>
#include<algorithm>
using namespace std;
int a[2010],q[2010];
int ans=0;
void arrange_sort(int l,int r)
{
    
    if(l>=r) return;
    int mid=l+r>>1;
    arrange_sort(l,mid);
    arrange_sort(mid+1,r);
    int k=0;
    int i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
    
// cout<<i<<' '<<j<<' '<<l<<' '<<r<<' '<<a[i]<<' '<<a[j]<<endl;
        if(a[i]<=a[j]) q[++k]=a[i++];
        else
        {
    
            q[++k]=a[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid) q[++k]=a[i++];
    while(j<=r) q[++k]=a[j++];
    for(int i=l,j=1;j<=k;j++,i++)
        a[i]=q[j];
}
int main()
{
    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    arrange_sort(1,n);
    cout<<ans<<endl;
}

树状数组法

#include<algorithm>
#include<iostream>
#include<unordered_map>
using namespace std;
unordered_map<int,int> a;
int lowbit(int x)
{
    
    return x&-x;
}
void insert(int x,int k)
{
    
    while(x<=0x3f3f3f3f)
    {
    
        a[x]+=k;
        x+=lowbit(x);
    }
}
int query(int x)
{
    
    int ans=0;
    while(x)
    {
    
        ans+=a[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
    
        int x;
        cin>>x;
        insert(x,1);
        ans+=i-query(x);
    }
    cout<<ans<<endl;
}