逆序对(deseq) 【问题】给定一个序列a1,a2,…,an，如果存在i < j并且ai > aj，那么我们称之为逆序对，求逆序对的数目 输入：第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。 输出：所有逆序对总数 样例输入： 4 3 2 3 2 样例输出： 3 用C语言实现

以下是使用归并排序思想求解逆序对的C语言代码：

#include <stdio.h>

// 归并排序，返回逆序对数目
int merge_sort(int a[], int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    int cnt = merge_sort(a, l, mid) + merge_sort(a, mid+1, r);
    int i = l, j = mid + 1, k = 0;
    int temp[r-l+1];
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
            cnt += mid - i + 1;  // 统计逆序对数量
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (int p = 0; p < k; p++) {
        a[l+p] = temp[p];
    }
    return cnt;
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    printf("%d\n", merge_sort(a, 0, n-1));
    return 0;
}

算法思路：

归并排序是一种经典的分治思想的排序算法，它的时间复杂度为 $O(n \log_2 n)$（$n$为数组长度）。在归并排序的过程中，我们将原数组分成左右两部分，分别进行排序，然后再将排序后的左右两部分合并成一个有序数组。在归并的过程中，我们统计左右两部分之间的逆序对数量，最后返回总的逆序对数量即可。

具体实现：

1. 首先，我们定义一个函数 `merge_sort`，它的参数有三个：数组 `a`、左边界 `l` 和右边界 `r`，表示对数组 `a` 的区间 `[l, r]` 进行排序。

2. 如果左边界 `l` 大于等于右边界 `r`，则不需要排序，返回0。

3. 将区间 `[l, r]` 分成两个部分，分别对左半部分 `[l, mid]` 和右半部分 `[mid+1, r]` 进行排序，其中 `mid = l + (r - l) / 2`。

4. 对左右两部分进行排序的同时，统计左右两部分之间的逆序对数量。具体实现是：设左半部分当前考虑到下标为 `i` 的元素，右半部分当前考虑到下标为 `j` 的元素，如果 `a[i] <= a[j]`，则将 `a[i]` 加入临时数组 `temp` 中，否则将 `a[j]` 加入 `temp` 中，并将逆序对数量加上左半部分剩余的元素个数 `mid - i + 1`。

5. 如果左半部分还有元素没有加入临时数组 `temp`，则将它们全部加入 `temp` 中。

6. 如果右半部分还有元素没有加入临时数组 `temp`，则将它们全部加入 `temp` 中。

7. 将临时数组 `temp` 中的元素复制到原数组 `a` 的相应位置。

8. 返回左右两部分之间的逆序对数量。

9. 在主函数中，读入数据后调用 `merge_sort` 函数，并输出返回值即可。

时间复杂度分析：

归并排序的时间复杂度为 $O(n \log_2 n)$，其中 $n$ 为数组长度。在归并的过程中，每次比较两个元素时，都会统计一次逆序对数量。因此，总的时间复杂度为 $O(n \log_2 n)$。