描述

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

思路

暴力出奇迹

对于每一个数都遍历一遍排在他前面的数，每有一个比他大的数就ans++，时间复杂度为$O(n^2)$，很明显这个算法只能应用于数很少的情况。

归并排序求逆序数

归并排序中，在每次合并的时候判断一下。

假设数列为9 1 0 5 4，先把它分成两个子序列，9 1 | 0 5 4，使左右分别有序，则有1 9 | 0 4 5，此时进行两个子序列合并。如果a[i]<=a[j],则i++，继续比较，如果a[i]>a[i],则说明a[i]到a[mid]的数都大于a[j],那么ans+=mid-i+1。

代码

ll a[500005],tem[500005],ans;       //a为要求的序列，tem是临时存放的数组

void divide(int low,int high)       //子序列
{
    if(high==low)                   //因为上面那种思路需要子序列有序，当子序列只有一个数时，即认为这个子序列有序
    return;
    divide(low,(low+high)/2);       //使左边有序
    divide((low+high)/2+1,high);    //使右边有序
    
    int mid=(low+high)/2; 
    int i=low,j=mid+1,k=low;
    while(i<=mid&&j<=high)          //合并
    {
        if(a[i]>a[j])
        {
            ans+=mid-i+1;
            tem[k++]=a[j++];
        }
        else
        tem[k++]=a[i++];
    }
    while(i<=mid) tem[k++]=a[i++];  //将剩下的存入数组
    while(j<=high) tem[k++]=a[j++];
    
    for(int t=low;t<=high;t++) a[t]=tem[t]; //更新a数组
    
    return;
}

用树状数组求逆序数

这个算法的思想就是依次插入序列的数，每插入一个就ans+=在这个数前面比它大的数的个数。最后的ans就是答案。

用一个数组tr[x],tr[x]=1代表x在序列中存在1个。一开始tr都为0，因为此时未插入任何数。

此时的树状数组tr[x]代表在x前lowbit(x)个数有多少个数比它小。

初始化tr数组为0，代表一开始所有数都没有插入。

每次插入一个数x就是tr[x]++,再更新一次树状数组，维护区间和。

离散化处理

根据上面的思路，我们很容易发现我们要开很大的数组。如果题目说长度为$5 \times 10^5$数列a中$a_i \leq 10^9$，这时候开$10^9$的数组就太浪费了，我们就可以离散化处理。

我们离散化的目的就是为了把$10^9$的数对应到$5 \times 10^5$中，举个例子：
原序列为： 999 23 0 98765 2 7
离散化后： 5 4 1 6 2 3
说白了就是用一个$1-n$的数列来代替原序列，而逆序数不变。

没看懂的可以跟着代码模拟一遍。

代码

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define lowbit(x) (x&(-x))
#define INF 0xffffffff
typedef long long ll;
const int N=5e5+5;
int tr[N],b[N],n;
typedef pair <ll,int> pp;
pp a[N];

void Update(int x)      //插入x
{
    while(x<=n)
    {
        tr[x]++;
        x+=lowbit(x);
    }
}

int Query(int x)    //查询序列中比x小的有多少个
{
    int sum=0;
    while(x>0)
    {
        sum+=tr[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n&&n)
    {
        CRL(tr);
        for(int i=1;i<=n;i++) //离散化开始
        {
            cin>>a[i].first;
            a[i].second=i;
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++) b[a[i].second]=i; //离散化结束，b数组即是离散化后的数组
        
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            Update(b[i]);				//依次插入更新
            ans+=(i-Query(b[i]));
        }
        cout<<ans<<endl;
    }
    return 0;
 }

题目

poj-2299

hdu-1394