题解：P1908 逆序对

· · 题解

水发题解
传送门

对于这种逆序对的题目，我们可以使用归并排序。

原理：分治

比如说我们有这样一个序列：

那么，我们可以把它劈分成两半，于是逆序对被分为三类：全在左边的、一半左边一半右边的、全在右边的。
第一类和第三类可以递归处理。

于是我们只需计算一半左边一半右边的的逆序对个数即可。
我们可以先把左右两边排序……

然后再利用双指针数出来对于每个右边的元素，有几个左边的元素比他大即可。我画的竟然没有夹在中间的逆序对，怎么回事呢。
于是我们可以顺理成章地在计算完之后使用归并排序。思路讲完了。

时间复杂度

设 T(n) 为当数据规模为 n 时的时间复杂度，则：

T(n)=2T(\frac{n}{2}) + O(n)

由主定理可知 T(n)=O(n\log{n})

后记

刚学完 cdq，发现这其实就是 cdq 简单版。