题目描述

意思就是求一个数组的逆序对个数

刚学了离散化，突然想起来之前学了树状数组，但是还不会用树状数组求逆序数，正好在这里试一试
树状数组及其求逆序数的方法看这篇博客就行
https://blog.csdn.net/bestsort/article/details/80796531

算法1

归并排序求逆序数，看上面秦淮岸大佬的就行了hhhhh

就是懒得复制blablabla

算法2

树状数组+离散化求逆序数。

因为数值范围过大0≤ai≤999999999，所以肯定要先离散化再进行后续操作。离散化后，根据算法进阶第202页的知识，树状数组与逆序数，就可以求出答案了。

复杂度对比

算法1的复杂度为O(NlogN) ，算法2不离散化的时候的复杂度为O((N+M)logM),M为数值范围的大小,当数值范围过大当然要先离散化再用树状数组进行计算。因为离散化本身就要通过排序来进实现，所以再这种情况下就不如直接用归并排序的方法计算逆序数了。

C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long int
using namespace std;
const int N=500005;
int n,z,vc[N],va[N];//va为离散化后的数组,vc为树状数组
int lowbit(int x){return x&-x;}

struct Node
{
    int v,order;//用于离散化
}a[N];//a为一开始读入数据的数组
bool cmp(Node a,Node b)
{
    return a.v<b.v;
}
void update(int x,int y,int n)//树状数组更新
{
    for(int i=x;i<=n;i+=lowbit(i))
        vc[i]+=y;
}
int getsum(int x)//树状数组求和
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans+=vc[i];
    return ans;
}
int main(void)
{

    while(scanf("%d",&n)&&n)
    {
        memset(vc,0,sizeof(vc));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].v);//读入a[i]的数据和位置，为后面的离散化做准备
            a[i].order=i;
        }
        sort(a+1,a+1+n,cmp);//对a数组按照a.v从小到大排序
        for(int i=1;i<=n;i++)
            va[a[i].order]=i;//离散化
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            update(va[i],1,n);
            ans+=i-getsum(va[i]);//树状数组求逆序对个数的方法
        }
        printf("%lld\n",ans);
    }
    return 0;
}