威风镰鼬

题解

/ 注册

全部文章 / 题解（共1篇）

题解 | #逆序数#

思路先看一眼数据范围，1e5逐个数逆序数是肯定会超时的；对于排序后的数组，每一个数前面序号比它大的数的个数就是它的逆序数，因此我们可以想到一种O(nlogn)排序并求逆序数的方法，只需要套一个归并排序的板子，然后统计归并排序时每个区域交换元素时相隔的元素个数就好了。代码 #include<...

排序归并排序逆序对

2021-06-12

1 564