归并排序求逆序对

一句话理解

归并求逆序对：合并时统计左段剩下的比右段当前更大的个数。

为什么要学

经典 n log n 算法。

讲解

右段取出一个 b 时，左段还没合并的都比 b 大，这些都构成逆序。

注意 long long 计数。

例子

左 [2,4] 右 [1,3]。先取 1，左段两个都比 1 大，贡献 2。再取 2，然后 3，左段剩 4 贡献 1。共 3。

常见错误

• 用 int 存答案溢出。
• 统计条件和 <、<= 搞反。