树状数组求逆序对数

发布于 2019-10-26  223 次阅读


前置芝士:树状数组

树状数组求逆序对数

逆序数的定义:对于一个数列$a_n$所有满足$a_i > a_j$ 且 $i < j$的二元组的个数称为逆序数。

做法

假如我们有一列数:

对于一个数$i$,我们把第$i$位++,之后在统计1 ~ i的区间和,这个区间和便是$i$的顺序对,用$i$再减去这个数即为逆序对。

为什么这样能行得通呢,我们回想一下逆序对的定义,$a_i > a_j$ 且 $i < j$的二元组,我们在按原数组顺序插入如的时候,其实已经保证了$i < j$,我们插入又恰恰满足了,$a_i > a_j$。

例如我们有以下元素:

$$2,1,4,7$$

我们从前往后插入进树状数组内,

先插入$2$,第$2$个位置的数据=1。

查询1~2的区间和,为$1$,所以他的顺序对数为$1$,逆序对数为$1-1=0$。

位置 1 2 3 4 5 6 7
树状数组 1
数据 1

再插入$1$,把第$1$个位置的数据=1。

查询1~1的区间和,为$1$,所以他的顺序对数为$1$,逆序对数为$2-1=1$。

位置 1 2 3 4 5 6 7
树状数组 1 1
数据 1 2

再插入$4$,把第$4$个位置的数据=1。

查询1~1的区间和,为$4$,所以他的顺序对数为$3$,逆序对数为$3-3=0$。

位置 1 2 3 4 5 6 7
树状数组 1 1 1
数据 1 2 1

再插入$7$,把第$7$个位置的数据=1。

查询1~1的区间和,为$4$,所以他的顺序对数为$4$,逆序对数为$4-4=0$。

位置 1 2 3 4 5 6 7
树状数组 1 1 1 1
数据 1 2 1 1

代码实现 以洛谷P1908 逆序对 为例

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

#define endl '\n'
#define maxn 500005

struct node
{
    long long data, rk;
    bool operator< (const node &b)const  //供排序用
    {
        if (data == b.data)
            return rk < b.rk;
        return data < b.data;
    }
} c[maxn];

long long n, a[maxn], _rank[maxn];

inline long long lowbit(long long x)
{
    return x & (-x);
}

inline void add(long long pos, long long x)
{
    for (register long long i = pos; i <= n; i += lowbit(i))
        a[i] += x;
}

inline long long sum(long long pos)
{
    long long sum = 0;
    for (register long long i = pos; i >= 1; i -= lowbit(i))
        sum += a[i];
    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (register long long i = 1; i <= n; i++) //输入数据
    {
        cin >> c[i].data;  
        c[i].rk = i; //c[i]在数组中的序号
    }

    sort(c + 1, c + n + 1); //排序(离散化)

    for (register long long i = 1; i <= n; i++)
        _rank[c[i].rk] = i; //求相对大小

    /*
    //  1 2 10000
    //  1 2 3
    //上面两个序列在本题是等效的,因为无论第三项是3还是10000,它都大于第一项和第二项

    我们的目标是把原先大的数缩小

    因为排完序的序列和原序列长度相同
    以1为例:
    我们令原先c[1].rk(即最小的数位置)等与1。
    接着我们令原先c[2].rk(即次小的数位置)等与2。
    这便起到缩小数据的作用
    */

    long long ans = 0;
    for (register long long i = 1; i <= n; i++)
    {
        add(_rank[i], 1);
        ans += i - sum(_rank[i]);  //求逆序对
    }
    cout << ans << endl;
    return 0;
}