排序 · 逆序对计数

排序 · 逆序对计数

给定 n 个整数，求逆序对的个数——即满足 i < j 且 a[i] > a[j] 的数对 (i, j) 的总数。

逆序对个数衡量数组“有多乱”：已升序 = 0；完全降序 = n(n-1)/2。归并排序能在 O(n log n) 顺带数出来（合并时右半元素先出，就和左半剩余个数构成逆序对）。

输入：第 1 行 n；第 2 行 n 个整数。
输出：逆序对个数。

例：输入 5 / 2 4 1 3 5 → 输出 3（(2,1)(4,1)(4,3)）。