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

这道题可以使用归并排序来解决，通过归并排序将序列分治为两个有序序列，然后再进行合并。在合并的过程中，统计逆序对的个数。

具体的做法是，在合并两个有序序列的过程中，如果左边的序列的当前元素大于右边的序列的当前元素，那么就存在逆序对。因为左边的序列是有序的，所以左边序列当前元素之后的所有元素都大于右边序列的当前元素，都可以与右边的当前元素组成逆序对。因此可以统计左边序列当前元素之后的元素个数，加入到逆序对的总数中。

下面是 C 语言的代码实现：

#include <stdio.h>

#define MAXN 100000

int a[MAXN], tmp[MAXN];

long long merge(int l, int m, int r) {
    int i = l, j = m + 1, k = 0;
    long long cnt = 0;
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            cnt += m - i + 1;
        }
    }
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (i = 0; i < k; ++i) a[l + i] = tmp[i];
    return cnt;
}

long long merge_sort(int l, int r) {
    if (l >= r) return 0;
    int m = (l + r) / 2;
    long long cnt = merge_sort(l, m) + merge_sort(m + 1, r);
    cnt += merge(l, m, r);
    return cnt;
}

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

时间复杂度为 O(nlogn)。