牛客 逆序数 （归并排序）

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

输入54 5 1 3 2

输出7

题目分析这是一个经典的归并排序的模板题，也是一个树状数组的模板题，但是我不会树状数组！！！，那我们现在来讲一下什么是归并排序。

• 首先就是递归，递归将一个数组分为两部分，然后再次递归将分完之后的每一部分分为两部分，然后不断地递归，直到每部分只剩下一个元素为止。
• 然后再从这无数个数据在逐渐的合并，用二路归并，每次归并我们都计算一下逆序对的数量然后累加，但是每次归并的数组都是临时数组，会在后面的归并中覆盖，二路归并前提是要是两个有序的数组，所以这就是为什么分到最后每一部分都是一个元素，因为一个元素再怎么都是有序的，然后从下往上去二路归并。
• 那么如何求逆序对的数量呢，在二路归并的时候，如果后面的数跑到前面去了，我们就计算中间路过了多少个数，那么它前面就有多少个数比它大。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
ll a[maxn], b[maxn], cnt;
void merge(ll l, ll mid, ll r)
{
    ll i = l, j = mid + 1, t = 1;
    while (i <= mid && j <= r)
    {
        if (a[i] > a[j])
        {
            b[t++] = a[j++];
            cnt += mid - i + 1; //记录逆序对数量
        }
        else
            b[t++] = a[i++];
    }
    //一个子序列中的数都处理完了，另一个还没有，把剩下的直接复制过来
    while (i <= mid)
        b[t++] = a[i++];
    while (j <= r)
        b[t++] = a[j++];
    for (int i = r; i >= l; i--)
        a[i] = b[--t]; //把排好序的b数组复制回a数组
}
void mergesort(ll l, ll r)
{
    if (l == r)
        return;
    int mid = (l + r) >> 1; //平均分为两个子序列
    mergesort(l, mid);
    mergesort(mid + 1, r);
    merge(l, mid, r); //合并
}
int main()
{
    ll n, k;
    while (~scanf("%lld", &n))
    {
        cnt = 0;
        for (ll i = 1; i <= n; ++i)
            scanf("%lld", &a[i]);
        mergesort(1, n); //归并排序
        printf("%lld\n", cnt);
    }
    return 0;
}