先贴个题目：

以及原题链接： 788. 逆序对的数量 - AcWing题库https://www.acwing.com/problem/content/790/

 这题也是板子题，就是对归并排序的衍生，我们先分析下如果用归并排序对排序区间进行二分的话，逆序对可能出现的情况：

第一种（红色）：都在左侧区；第二种（黄色）：一个在左侧区间，一个在右侧区间；第三种（蓝色）：都在右侧区间 。

我们考虑一下极限情况，归并的递归到最底层，左右都只有一个元素的情况，就可以发现，只存在情况2，而在往上一层，由于左右区间已被排序且在递归的上一层已经算过了逆序对，所以第一第三种情况也不存在，所以层层递归上去，我们唯一要考虑的就是第二种情况，因此就有了我们的代码：

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];
long long ans = 0;

void gbsort(int left, int right, int list[])
{
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    gbsort(left, mid, list);
    gbsort(mid + 1, right, list);
    int x = left, y = mid + 1, z = 0;
    while (x < mid + 1 && y < right + 1)
    {
        if (list[x] <= list[y])
        {

            tmp[z++] = list[x++];
        }
        else
        {
            ans += mid - x + 1;
            tmp[z++] = list[y++];
        }
    }
    while (x < mid + 1)
    {
        tmp[z++] = list[x++];
    }
    while (y < right + 1)
    {
        
        tmp[z++] = list[y++];
    }
    for (int i = 0; i < z;++i)
        list[left + i] = tmp[i];
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    gbsort(0, n - 1, a);
    cout << ans;
    return 0;
}

代码就基本上是套归并的板子，没什么好说的。

by————2024.3.1刷题记录