逆序对

一句话理解

逆序对是前面的数大于后面的数的对数。

为什么要学

衡量序列乱序程度，归并、树状数组都会算它。

讲解

暴力 O(n²) 枚举 i<j 且 a[i]>a[j]。n=1e5 要用 n log n。

冒泡交换次数等于逆序对数。

例子

[3,2,1] 有三对： (3,2)(3,1)(2,1)。

常见错误

• 把相等也当逆序。通常不算。
• n=1e5 暴力。