【练习】逆序数

逆序数

https://ac.nowcoder.com/acm/problem/15163

题目

题目描述：

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。

一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2。

那么这个序列的逆序数为7，逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。

输入描述：

第一行有一个整数n(1 <= n <= 100000), 然后第二行跟着n个整数，对于第i个数a[i]，(0 <= a[i] <= 100000)。

输出描述：

输出这个序列中的逆序数。

解析

求逆序数，我相信大家学过线代的一定都很熟了，逆序数怎么算。

就是求每一个数前面有多少个比自己要大的数呗（或者后面有多少比自己小也行）。

知识点

这道题的知识点可以很多：线段树，树状数组，归并排序（因为我只会归并排序的，所以我们就归并吧）。

归并排序

我们就先简单的来讲一下，归并排序时怎么归的。
我们首先就是递归的，将一个数组分成左右两个部分。直到每个部分只剩下一个为止。
然后在从这无数个一个的数据再逐渐的合并，合并用什么呢？就用二路归并。
）别吐槽我字丑
二路归并咋整呢？其实就是两个有序的序列，用两个指针分别指着他们的头，然后比大小放进去就行了。

算法讲解

既然我们已经归并排序怎么归的了，那我们就要知道他怎么求逆序数了。
首先我们要知道归并是利用了什么求出来的逆序数：在二路归并的时候，如果序列后面的数跑到前面来了，中间路过了多少个数，他前面就有多少个数比他大。
这不就正好是，计算前面有多少个数比他大的过程吗嘿嘿。
所以我们就在二路归并的时候计数器累加一下就好了。

算法操作

我们已经知道是归并排序了，而且知道了原理，我就直接来讲一下怎么用吧。

首先是归并分块，将一个区间递归分块：

int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);

递归到区间长度为1为止：
```
if (l == r) return;
```
然后我们就可以进行二路归并了。

二路归并我们考虑从区间首位置（l）和区间中间（mid+1）开始，为两个区间，开始二路归并：

while (x <= mid && y <= r) {
    if (info[x] > info[y]) {
        tmp[pos++] = info[y++];
        ans += mid - x + 1;
    }
        //如果前面的数大于后面的，说明我们在临时数组要保存后面的
        //既然是要保存后面的，说明后面那个数要跳跃mid - x + 1个到前面来
        else {
        tmp[pos++] = info[x++];
    }
}

为什么是mid - x + 1？因为每次往前跳就是跳第一段区间还剩下来的位置。为什么不加mid + 1到y的距离？因为前面的已经拿走了啊。

当其中一路判断完之后呢，我们就可以把另外一路剩下来的放进来了：
```
while (x <= mid) tmp[pos++] = info[x++];
while (y <= r) tmp[pos++] = info[y++];
```

最后吧这些放回原来的数组就好：

for (int i = r; i >= l; i--) info[i] = tmp[--pos];

打代码

首先是输入我们的数据。
接下来就按照我们上面说的操作进行归并排序。
然后看我完整代码吧~

AC代码

#include <iostream>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 7;
int n, info[MAX], tmp[MAX];
ll ans;
//全局变量区

void merge(int l, int mid, int r);
void merge_sort(int l, int r);
//函数预定义区

int main() {
    IOS;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> info[i];
    merge_sort(1, n);
    cout << ans << endl;
    return 0;
}
void merge_sort(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    merge(l, mid, r);
}
void merge(int l, int mid, int r) {
    int x = l, y = mid + 1;//左右进行二路归并
    int pos = 1;//记录临时数组的最大位置
    while (x <= mid && y <= r) {
        if (info[x] > info[y]) {
            tmp[pos++] = info[y++];
            ans += mid - x + 1;
        }
               //如果前面的数大于后面的，说明我们在临时数组要保存后面的
                //既然是要保存后面的，说明后面那个数要跳跃mid - x + 1个到前面来
                else {
            tmp[pos++] = info[x++];
        }
    }
    while (x <= mid) tmp[pos++] = info[x++];
    while (y <= r) tmp[pos++] = info[y++];
    for (int i = r; i >= l; i--) info[i] = tmp[--pos];
}
//函数区

牛客算法竞赛入门课题解文章被收录于专栏

憨憨的专栏