题目

题目描述:
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。
一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为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)。

输出描述:
输出这个序列中的逆序数。


解析

求逆序数,我相信大家学过线代的一定都很熟了,逆序数怎么算。
就是求每一个数前面有多少个比自己要大的数呗(或者后面有多少比自己小也行)。

知识点

这道题的知识点可以很多:线段树树状数组归并排序(因为我只会归并排序的,所以我们就归并吧)。

归并排序

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

算法讲解

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

算法操作

  1. 我们已经知道是归并排序了,而且知道了原理,我就直接来讲一下怎么用吧。
  2. 首先是归并分块,将一个区间递归分块
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
  3. 递归到区间长度为1为止
    if (l == r) return;
  4. 然后我们就可以进行二路归并了。
  5. 二路归并我们考虑从区间首位置(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的距离?因为前面的已经拿走了啊。
  6. 当其中一路判断完之后呢,我们就可以把另外一路剩下来的放进来了:
    while (x <= mid) tmp[pos++] = info[x++];
    while (y <= r) tmp[pos++] = info[y++];
  7. 最后吧这些放回原来的数组就好:
    for (int i = r; i >= l; i--) info[i] = tmp[--pos];

打代码

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


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];
}
//函数区