帮我用c语言写逆序对(deseq) [3*] 逆序对(deseq) 【问题】给定一个序列a1,a2,…,an，如果存在i < j并且ai > aj，那么我们称之为逆序对，求逆序对的数目 输入：第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。 输出：所有逆序对总数 样例输入： 4 3 2 3 2 样例输出： 3 数据范围：N<=10^5。Ai<=10^5。时间限制为1s。

以下是一个基于归并排序的求逆序对的C语言代码实现：

#include <stdio.h>

#define MAXN 100000

int n;
int a[MAXN+1];
int tmp[MAXN+1];

long long merge_sort(int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) / 2;
    long long ans = merge_sort(l, mid) + merge_sort(mid+1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            ans += mid - i + 1;
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (i = l, k = 0; i <= r; ++i, ++k) {
        a[i] = tmp[k];
    }
    return ans;
}

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

主要思路是利用归并排序，在合并的过程中统计逆序对的数量。具体来说，在合并两个有序数组时，如果左边的数组元素 `a[i]` 大于右边数组元素 `a[j]`，那么左边数组剩余的元素都大于 `a[j]`，因此逆序对的数量就增加了 `mid - i + 1`，其中 `mid` 是左边数组的末尾。最后将两个有序数组合并成一个有序数组即可。

时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。