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

树状数组求逆序对

2024-09-24 00:09:37   217人阅读

逆序对指的是这样一种东西，在一个序列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;
}

 

树状数组求逆序对


联系
我们