求解逆序数

一、逆序数的定义

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。 一个排列中所有逆序的总数叫做这个排列的逆序数。比如1,2,4,3这个序列，逆序数为1。

二、暴力求解

暴力求解是最容易想到的办法，也是实现起来最简单的，只不过时间复杂度为O(n^2^)

代码：

1
2
3
4
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (nums[i] > nums[j])
            ans++;

洛谷模板题评测结果：

ScreenShot_2024-09-16_15-28-21

时间复杂度O(n^2^)，很容易就TLE了。

三、归并排序求解逆序数

简单来说，归并排序就是先让子序列有序，然后再合并子序列，使得整个序列都是有序的。

在将归并排序应用于求逆序数之前，我们需要知道这样一个规律，改变局部序列的顺序，是不会影响其他部分的逆序数的，因为无论被改变的序列顺序如何，他们的前后位置是一定的。举个例子：

序列6,5,2,1,4,7，此时后面四个数的逆序数之和为1

我们改变前两个数的顺序，得到一个新的序列5,6,2,1,4,7 此时，后面四个数的逆序数之和仍为1

再进一步思考。假设还是上面的序列6,5,2,1,4,7我们将其分成两部分6,5,2和1,4,7 ，两部分的逆序数分别为3和0，两部分合并后，增加的逆序数为3 + 2 + 0 = 5（对于元素1，新增3，对于元素4，新增2，对于元素7，新增0）。

解释：

1与前面的6,5,2构成3个，4与前面的6,5构成2个，7没有构成任何新的逆序

那么整个序列的逆序数为，3 + 5 = 8。

那么该如何快速的知道对于后半部分的每一个元素，新增的逆序数是多少呢？其实很简单，只要比前半部分元素小，那肯定就是一个逆序数了。比如1，前面的6,5,2都比他小，就是增加了3个。那么还要遍历整个前半部分序列，来数有几个元素比1小吗？这样做当然可以，但没必要。

此时我们根据最开始得出的规律“局部改变序列的顺序，是不会影响其他部分的逆序数的”，那我们保证两部分的序列都是有序的，即2,5,6与1,4,7 。然后将这两部分合并，使整个序列有序。我们使用辅助数组来完成这个操作。不难发现，当我们插入右侧序列中的元素的时候，此时左侧序列中剩余的元素的个数就是增加的逆序数。

ScreenShot_2024-09-16_16-09-15

根据图示，得到合并后增加的逆序数为：3 + 2 = 5。看到这个图，我们还很容易就会想到归并排序的合并过程，那我们是不是可以利用归并排序，然后在子序列合并的过程中记录下增加的逆序数呢？

当序列只有一个元素的时候，逆序数为0，而归并排序中，最小序列长度也是1，所以我们只需要用一个计数器，统计每次合并后产生的增加的逆序数即可。

ScreenShot_2024-09-16_16-18-18

所以得出逆序数为：1 + 1 + 4 = 6

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
using namespace std;

long long ans = 0; // 因为洛谷那一题会爆int所以用了long long
int a[500005];

void Merge(int a[], int low, int mid, int high)
{
    int b[high - low + 1];
    int p1 = low;
    int p2 = mid + 1;
    int cnt = 0;
    while (p1 <= mid && p2 <= high)
        if (a[p1] <= a[p2])
            b[cnt++] = a[p1++];
        else
        {
            b[cnt++] = a[p2++];
            ans += mid - p1 + 1; // 只是在归并排序的基础上加了一句统计的
        }
    while (p1 <= mid)
        b[cnt++] = a[p1++];
    while (p2 <= high)
        b[cnt++] = a[p2++];
    for (int i = 0; i < cnt; i++)
        a[i + low] = b[i];
}

void mergesort(int a[], int low, int high)
{
    int mid = (low + high) / 2;
    if (low == high)
        return;
    else
    {
        mergesort(a, low, mid);
        mergesort(a, mid + 1, high);
        Merge(a, low, mid, high);
    }
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    mergesort(a, 0, n - 1);
    cout << ans;
    return 0;
}

洛谷模板题评测结果：

ScreenShot_2024-09-16_16-23-31

使用归并排序求解，时间复杂度为O(nlog2n)可以通过此题。

四、树状数组求解逆序数

对于要求的序列a[i]，开辟一个长度为a序列中最大值的数组b[i]，并且初始化所有元素为0。然后遍历a[i]将b[a[i]]的值修改为1。

其实这个b数组的含义就是，b[i]为0则代表i这个元素还没遍历过，b[i]不是0，则代表i这个元素已经出现过b[i]次了。

每一次遍历都计算一下b[i+1]到b[n]所有元素的和sum，并修改计数器cnt = cnt + sum，因为先出现的，但是比a[i]大的会构成逆序对

举一个例子：(i从1开始)

遍历序列3,6,7,1：

对与3，此时sum = 0，因此cnt = cnt + 0 = 0;

对与6，此时sum = 0，因此cnt = cnt + 0 = 0;

对与7，此时sum = 0，因此cnt = cnt + 0 = 0;

对与1，此时sum = 3，因此cnt = cnt + 3 = 3;

所以逆序数为3。

这里会经常用到sum这个变量，所以可以维护一个b的前缀和数组，这样在使用sum的时候可以直接访问，而不需要遍历求和。但是最基础的前缀和显然是不够用的，因为我们在遍历a的时候，会经常对b的某一个元素进行更改，更改后会使得后续所有元素的前缀和改变，为保证其正确性，就必须给后面的所有值重新赋值，最坏时间复杂度会达到O(n^2)

有一种数据结构，叫树状数组。这个数据结构可以解决大部分区间上面的修改以及查询的问题，比如我们现在所遇到的sum值的求解。

在使用树状数组之前，我们先对数据存储进行优化。之前b[i]数组的长度是a[i]中的最大值，如果有一组数据是1,2,3,99999我们需要99999长度的数组，但是有效数据只有4个，太浪费了。我们可以对数据进行离散化，只需要和a[i]等长即可。

离散化：

一个新的数组d[i]与a[i]等长，d[i]表示在原数组中，第i大的元素在原数组中的位置。

比如1,5,2,3 d[1] = 2; d[2] = 4 ...

举个例子：

序列a = {5,3,4,2,1}离散化后d = {1,3,2,4,5}，我们直接遍历d[i]进行后续的计算。有一点需要注意，离散化后，我们求的不再是逆序数而是顺序数。一步步分析一下：

对与1，树状数组中比1小的元素数量为0，因此cnt = cnt + 0 = 0;

对与3，树状数组中比3小的元素数量为1，因此cnt = cnt + 1 = 1;

对与2，树状数组中比2小的元素数量为1，因此cnt = cnt + 1 = 2;

对与4，树状数组中比4小的元素数量为3，因此cnt = cnt + 3 = 5;

对与5，树状数组中比5小的元素数量为4，因此cnt = cnt + 4 = 9;

所以答案为9。

为什么是顺序数？：因为d[i]是从最大元素到最小元素在原数组中的位置，即元素越大的，在d中值越小，那么，大元素先出现会与后面的小元素构成逆序，与位置靠前的会与位置靠后的构成顺序，是等价的

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>

using namespace std;
#define M 500005
int a[M], d[M], t[M], n;

int lowbit(int x)
{
    return x & -x;
}
void add(int x) // 更新节点数值
{
    while (x <= n)
    {
        t[x]++;
        x += lowbit(x);
    }
}

int sum(int x) // 查询1~X的前缀和
{
    int res = 0;
    while (x >= 1)
    {
        res += t[x];
        x -= lowbit(x);
    }
    return res;
}

bool cmp(int x, int y) // 离散化比较函数
{
    if (a[x] == a[y])
        return x > y;   // 避免元素相同,因为元素相同，是不构成逆序的
    return a[x] > a[y]; // 按照原序列第几大排列
}

int main()
{
    long long ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], d[i] = i;

    sort(d + 1, d + n + 1, cmp); // 离散化

    for (int i = 1; i <= n; i++)
    {
        add(d[i]);            // 把这个数放进去
        ans += sum(d[i] - 1); // 累加
    }
    cout << ans;
    return 0;
}

洛谷模板题评测结果：

ScreenShot_2024-09-16_20-15-12