P1750 求逆序对

逆序对可以使用归并排序来解决。在归并排序中，我们将数组分成两个部分，然后递归地对它们进行排序，最后将它们合并在一起。在合并两个已排序的子数组时，我们可以计算逆序对的数量。具体地，我们用两个指针 $i$ 和 $j$ 分别指向两个子数组的开头，比较它们指向的元素的大小，如果 $a[i] \leq a[j]$，则已经不存在逆序对，直接将 $a[i]$ 加入合并后的数组中，并将 $i$ 指针向后移动一位；否则，将 $a[j]$ 加入合并后的数组中，并将 $j$ 指针向后移动一位，此时 $a[i+1..mid]$ 与 $a[j]$ 都是逆序对。

下面给出具体的代码实现：

const int N = 1e5 + 5;

int a[N], b[N], tmp[N]; // b 为辅助数组

long long merge(int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    long long cnt = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
            cnt += mid - i + 1; // 统计逆序对数量
        }
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= r) b[k++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = b[i];
    return cnt;
}

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

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

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