树状数组离散化求逆序对

莊·3001 · 2019-02-13 14:09:29 · 个人记录

如上，树状数组可以很好地求出一个随机序列中的逆序对的个数。

我们维护一个数组，其中下标为i的元素表示序列中i出现的次数。

但是当数据范围是N=1e6,而a[i]=1e9时，开一个下标为1e9的树状数组可能会MLE，所以我们需要将a数组离散化一下。

所谓离散化，就是用一个数在一个序列中的排名代替这个值。比如，原数组A={1412.3125,4126.1242,136.1,0,-11}，离散化之后：A'={4,5,3,2,1}这样我们之前可能要用map<double,int>,现在定义一个容量为5的数组就可以维护A数组了。

典型的离散化写法有两种。

用vector：

vector<int>id;

void dis()
{
    for(int i=1;i<=n;i++)
      id.push_back(a[i]);
    sort(id.begin(),id.end());
    id.erase(unique(id.begin(),id.end()),id.end());
    for(int i=1;i<=n;i++)
      a[i]=lower_bound(id.begin(),id.end(),i)-id.begin()+1;
}

不用vector：

pair<int,int>a[N];
int rank[N];

void dis()
{
    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++)
      rank[i]=a[i].second;
}

用了离散化之后，再维护就容易了。

我们先把树状数组中的rank[i]项加上1，然后查询1-rank[i]这段区间的和，每次用i减去查询和，用累加器将每一次的结果加起来，就是最终的答案了。

题目：P1908、P1116.

贴上一个P1116的代码。

#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 10005
using namespace std;
pair<int,int>a[N];
int rank[N];
int n;

//建议大家将线段树、树状数组、ST表之类的数据结构写在一个结构体里面。
//这样易于与别的函数区分开来。
class Binary_indexed_tree{
    private:
        int t[N];
        inline int lowbit(int);
    public:
        void update(int,int);
        int query(int);
}cnt;

inline int Binary_indexed_tree::lowbit(int k)
{return k&(-k);}

void Binary_indexed_tree::update(int x,int k)
{
    for(;x<=n;x+=lowbit(x))
      t[x]+=k;
}

int Binary_indexed_tree::query(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x))
      ans+=t[x];
    return ans;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].first);
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
      rank[i]=a[i].second;
    int answer=0;
    for(int i=1;i<=n;i++)
    {
        cnt.update(rank[i],1);
        answer+=i-cnt.query(rank[i]);
    }
    cout<<answer<<endl;
    return 0;
}