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

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

#include <stdio.h>
#define MAXN 1000005

int a[MAXN], tmp[MAXN];

long long merge_sort(int l, int r) {
    if (l >= r) return 0;

    int mid = (l + r) >> 1;
    long long ans = merge_sort(l, mid) + merge_sort(mid+1, r);

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

    for (i = l; i <= r; i++) a[i] = tmp[i];

    return ans;
}

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    printf("%lld\n", merge_sort(0, n-1));

    return 0;
}

时间复杂度为 $O(n\log n)$，其中 $n$ 为序列长度。