AcWing 788 逆序对的数量

788. 逆序对的数量 - AcWing题库

逆序对，即位置顺序与大小顺序不符的数对，也就是对于一个期望升序的序列Num[]，当i<j时，Num[i]>Num[j]

这道题要求求出逆序对的个数，显然在归并排序的过程中我们就是在逐步的消除逆序对，所以我们可以在递归的排序过程中求出逆序对的个数

已知归并排序是通过前后两个子列来进行归并的且通过递归的操作我们已知进行归并的两个子列在其内部都是有序的，因此可以知道，子列内部是不存在逆序对的

所以逆序对的两元素仅分别存在于两个子列中，在有第一子列下标<第二子列下标，可知只有出现第一子列的元素小于第二子列(第二子列的元素大于第一子列)的情况下才会出现逆序对

假设第一子列指针L已经指到了元素A，第二子列的指针R指到了元素B，且此时B<A,则认为此时出现了上述请况

由于第一子列已经升序排列，所以可以知道，B不仅大于A，还大于A到子列尾的所有数，可知道一共mid-L+1个数，因此由B引起的逆序对的数量就为mid-L+1。

而且，在求完一次归并的逆序对后，经过此次归并，由元素A形成的逆序对就消除了，因此不必担心后续的计算会重复

到这里，相信聪明的你已经知道如何求出逆序对的数量了。

最后一点提醒，当当前两个子列的指针指到的当前元素相等的时候，我们务必选择将第一子列的元素移入存储数组而不是第二子列的元素，因为第二子列的元素是引起逆序对的因素，如果将其移出第二子列，可能会导致后续的逆序对数量缺少，而第一子列的移动不会影响

附上AC代码，当然还要注意开long long ，这题的逆序对数量有的会爆int(不开 long long 见祖宗）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int Temp[N];
long long  Num = 0;
void merge_sort(int p[], int L, int R)
{
    if (L >= R)return;
    int mid = L + R >> 1;
    merge_sort(p, L, mid);
    merge_sort(p, mid + 1, R);
    int l = L; int r = mid + 1;
    int k = 0;
    while (l <= mid && r <= R)
    {
        if (p[l] <= p[r])//这里的等于很重要
            Temp[k++] = p[l++];
        else
        {
            Num += (mid - l + 1);
            Temp[k++] = p[r++];
        }
    }
    while (l <= mid)Temp[k++] = p[l++];
    while (r <= R)Temp[k++] = p[r++];
    for (int j = 0; L <= R; L++, j++)
        p[L] = Temp[j];
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", q + i);
    merge_sort(q, 0, n - 1);
    printf("%lld", Num);
}

给出一个错误案例

    if (p[l] < p[r])
            Temp[k++] = p[l++];
        else
        {
            if(p[l]>p[r])
            Num += (mid - l + 1);//这里就是相等时也选择移动第二子列，会使得逆序对数量减少（可能）
            Temp[k++] = p[r++];
        }