首页 > 代码库 > 树状数组求逆序对

树状数组求逆序对

逆序对指的是这样一种东西,在一个序列x中,某两个数x[i]和x[j]满足x[i]>x[j],且i<j。luogu有很多题可以练习这种题,例如我今天做的火柴排队(NOIP2013),再例如P1908逆序对

 

逆序对有很多种求法,在数据规模较小的时候可以n2暴力,较大的可以归并,树状数组解法是一种树状数组优化的暴力。

由于标题是树状数组求逆序对,我们就先不说别的,先看看和树状数组有关的暴力::

假设输入是这样的:

q [ 5 3 4 2 1 ]

这时我们设一个指针变量。从n到1遍历q数组。再设一个c数组,c[i]表示值为i的数在遍历过程中出现了几次。

初始的c数组是这样的:c [ 0 0 0 0 0 ],表示遍历过程中(其实还没开始遍历),1、2、3、4、5这五个数都没有出现过。

回到刚才的指针变量,名字暂定为k。此时k=5,q[k]=1。

于是从1到q[k]遍历c数组(设为j),如果遍历过程中发现c[j]值不为零,则说明q[k]和j构成一个逆序对,且逆序对的个数等于c[j]。很明显,现在并没有。

然后让c[q[k]]++,表示遍历过程中q[k]这个值出现了一次。

k--     ----------->   k=4 , q[k]=2。   c [ 1 0 0 0 0 ]

从1到q[k]遍历c数组,发现总共有1个数,在q[k]之前出现过(即c[1]),因此可以跟q[k]组成逆序对的数有1个。

然后让c[q[k]]++,表示遍历过程中q[k]这个值出现了一次。

k--     ----------->   k=3 , q[k]=4。   c [ 1 1 0 0 0 ]

从1到q[k]遍历c数组,发现总共有2个数,在q[k]之前出现过(即c[1]和c[2]),因此可以跟q[k]组成逆序对的数有2个。

然后让c[q[k]]++,表示遍历过程中q[k]这个值出现了一次。

以此类推。

但是为什么可以这样呢?

首先我们发现,我们是倒着遍历q数组的。这说明在查询过程中,假设发现c数组有一个单元不为零,那么可以断定这个数比q[k]先被遍历到。又因为倒着遍历q数组,所以在输入数据q[]中,这个数的编号比q[k]靠后。

又因为c数组储存的是值,也就是说,找到的数肯定比q[k]小

这就是逆序对的性质对不对

上代码

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template <typename T>
T read(){
    T num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch==-)    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-0;
        ch=getchar();
    }
    return num*f;
}
#define read()    read<long long>()
int tree[50000];
struct file{
    int id;
    int data;
}q[56000];
long long ans=0;
int n;
void add(int k,int num){
    while(k<=n){
        tree[k]+=num;
        k+=k&(-k);
    }
}

void find(int k){
    int i=k;
    while(k){
        ans+=tree[k];
        k-=k&(-k);
    }
    add(i,1);
}
bool cmp1(file a,file b){
    return a.data<b.data;
}

bool cmp2(file a,file b){
    return a.id<b.id;
}

int main(){
    n=read();
    for(int i=1;i<=n;++i){
        q[i].data=read();
        q[i].id=i;
    }
    sort(q+1,q+n+1,cmp1);
    int dt=1;
    for(int i=1;i<=n;++i){
        if(q[i].data=http://www.mamicode.com/=q[i-1].data){
            q[i].data=q[i-1].data;
        }
        else q[i].data=http://www.mamicode.com/dt++;
    }
    sort(q+1,q+n+1,cmp2);
    for(int i=n;i>=1;--i){
        find(q[i].data);
    }
    printf("%lld",ans);
    return 0;
}

 

树状数组求逆序对