分治策略逆序对计数C语言实现

下面是一个C语言实现分治策略逆序对计数的示例代码：

#include <stdio.h>
#define MAX 100000

int a[MAX], tmp[MAX], cnt;

void mergeSort(int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(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++];
            cnt += mid - i + 1;
        }
    }
    while (i <= mid)
        tmp[k++] = a[i++];
    while (j <= r)
        tmp[k++] = a[j++];
    for (int i = l; i <= r; i++)
        a[i] = tmp[i];
}

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

这段代码中，使用了一个全局变量`cnt`来保存逆序对的数量，`mergeSort`函数实现了归并排序和计算逆序对的过程。在归并排序的过程中，如果左边的元素大于右边的元素，则说明存在逆序对，并且逆序对数量等于左边剩余元素的个数。最后，将数组排序完成后，输出逆序对数量即可。