$\color{green}{<–画图不易，点下这里赞一下吧}$

逆序对的定义：在一个数字数组中，如果存在索引 i 和 j（其中 i < j），使得 arr[i] > arr[j]，则称其为一个逆序对。

暴力解法：

• 最简单的计算逆序对的方法是通过两层嵌套循环遍历数组，比较每一对元素，并在找到逆序对时递增计数器。然而，这种方法的时间复杂度为 O(n^2)，对于大型数组可能效率较低。

基于归并排序的解法

一种高效的计算逆序对的方法是使用修改后的归并排序算法。基本思想是将数组分割为较小的子数组，递归地对它们进行排序，然后在合并过程中计算逆序对。

• 归并排序步骤：将数组递归地分割为两半，直到每个子数组只有一个元素。然后，将子数组按照排序顺序合并回来，同时在合并过程中计算逆序对。

• 合并过程中计算逆序对：在合并两个已排序的子数组时，如果发现逆序对（即 arr[i] > arr[j]），则将逆序对的数量递增为第一个子数组中剩余的元素数量（即 (mid - i + 1)，其中 mid 是合并的子数组的中间索引）。

• 这是因为在合并过程中，如果左边的子数组元素 arr[i] 大于右边的子数组元素 arr[j]，则 arr[i] 大于右边子数组中的所有元素，形成逆序对。

示例

假设一个数组 arr = [4, 3, 2, 1]。

使用基于归并排序的方法，我们可以如下计算逆序对的数量：

• 初始数组：[4, 3, 2, 1]

• 归并排序步骤1：[4, 3, 2, 1] -> [4, 3], [2, 1]

• 归并排序步骤2：[4, 3], [2, 1] -> [4], [3], [2], [1]

• 归并排序步骤3：合并 [4], [3]，得到[3, 4]

• 合并过程中计算逆序对： [4] 与 [3] 合并，总逆序对数量 = 1（因为 4 > 3 且 且 4 后面没有其他元素）

• 归并排序步骤4：合并 [2], [1], 得到[1, 2]

• 合并过程中计算逆序对： [2] 与 [1] 合并，总逆序对数量 = 1（因为 2 > 1 且 且 2 后面没有其他元素）

• 归并排序步骤5：[3, 4], [1, 2] -> [1, 2, 3, 4]

• 合并过程中计算逆序对：[3, 4] 与 [1, 2] 合并，总逆序对数量 = 4（最开始 3 和 1 比较，因为 3 > 1, 所以逆序对为 mid - l + 1 = 1 - 0 + 1 = 2 个。 接下来3 与 2 比较：因为 3 > 2, 所以逆序对为 mid - l + 1 = 1 - 0 + 1 = 2 个。）

• 最终逆序对数量：1 + 1 + 2 + 2 = 6

- 时间复杂度：该方法的时间复杂度为 O(n log n)。

• 归并排序合并过程中计算逆序对数量
• 若 a[i] > a[j]，则a[i] 和它后面的元素都大于 a[j]，a[i] 构成逆序对数量：res += mid - i + 1;

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int temp[N];

long long find(int a[], int l, int r){
    if(l >= r) return 0;
    int mid = l + (r - l >> 1);
    long long res = 0;
    res += find(a, l, mid);
    res += find(a, mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) temp[k++] = a[i++];
        else
        {
            temp[k++] = a[j++];
            res += mid - i + 1;
        }
    }
    while(i <= mid) temp[k++] = a[i++];
    while(j <= r) temp[k++] = a[j++];

    for(i = l,k = 0;i <= r;i++)
        a[i] = temp[k++];
    return res;


}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n;i++){
        cin >> a[i];
    }
    cout << find(a, 0 ,n - 1);
}