求逆序对数的三种方法

0 前言

总结一下三种求逆序对数的方法

1 定义

逆序对：序列 中，满足 且 的有序数对 .

2 算法

2.1 归并法

2.1.1 算法原理

本质就是CDQ分治，在归并排序合并的过程中处理逆序对数，计算右区间的每一位数字对已排好序的左区间的贡献

时间复杂度 .

2.1.2 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

int n;
int a[N];

long long mergesort(int *arr, int l, int r)
{
    if (l == r)
        return 0;
    int mid = (l + r) >> 1;
    long long res = 0;
    res += mergesort(arr, l, mid);
    res += mergesort(arr, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    int *tmp = (int *)malloc(sizeof(int) * (r - l + 1));
    while (i <= mid && j <= r)
        if (a[i] <= a[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++], res += mid - i + 1;
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];
    for (int p = 0; p < k; p++)
        arr[l + p] = tmp[p];
    free(tmp);
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    printf("%lld\n", mergesort(a, 1, n));
    return 0;
}

2.2 权值树状数组法

2.2.1 算法原理

对于第 的数字 ，我们考虑计算该位能组成的逆序对的个数

对前 位建立权值树状数组，每次查询在区间 内比 小的数字个数，将其累加，即为逆序对个数

时间复杂度 .

2.2.2 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

int n, m;
int a[N];

struct BIT
{
    int c[N];
    inline int lowbit(int x)
    {
        return x & -x;
    }
    inline void modify(int pos, int val)
    {
        for (int u = pos; u <= m; u += lowbit(u))
            c[u] += val;
    }
    inline int query(int pos)
    {
        int res = 0;
        for (int u = pos; u; u -= lowbit(u))
            res += c[u];
        return res;
    }
} T;

int buc[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        buc[i] = a[i];
    }
    sort(buc + 1, buc + n + 1);
    m = unique(buc + 1, buc + n + 1) - buc - 1;
    long long ans = 0;
    for (int i = n; i >= 1; i--)
    {
        int k = lower_bound(buc + 1, buc + m + 1, a[i]) - buc;
        ans += T.query(k - 1);
        T.modify(k, 1);
    }
    printf("%lld\n", ans);
    return 0;
}

2.3 权值线段树法

2.3.1 算法原理

和权值树状数组一个意思，只不过使用权值线段树实现

时间复杂度 .

2.3.2 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

struct SegmentTree
{
    int data[N << 2];
    void modify(int p, int l, int r, int val)
    {
        ++data[p];
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        if (val <= mid)
            modify(p << 1, l, mid, val);
        else
            modify(p << 1 | 1, mid + 1, r, val);
    }
    int query(int p, int l, int r, int val)
    {
        if (data[p] == 0)
            return 0;
        if (l >= val)
            return data[p];
        int mid = (l + r) >> 1;
        if (val <= mid)
            return query(p << 1, l, mid, val) + query(p << 1 | 1, mid + 1, r, val);
        else
            return query(p << 1 | 1, mid + 1, r, val);
    }
} T;

int n;
int a[N];

int buc[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        buc[i] = a[i];
    sort(buc + 1, buc + n + 1);
    int m = unique(buc + 1, buc + n + 1) - buc - 1;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int k = lower_bound(buc + 1, buc + m + 1, a[i]) - buc;
        ans += T.query(1, 1, m, k + 1);
        T.modify(1, 1, m, k);
    }
    printf("%lld\n", ans);
    return 0;
}