区间逆序对做到 o(n^1.5) 的方法

· · 题解

设 m=\Theta(n)。

对值域分块，设块数为 b。

对于每块内的贡献，我们发现这里只有 O(\dfrac {n^2} b) 对二元组，所以做一个二维数点即可。对于 b=n^e，因为存在 O(n^{eps})-O(1) 的分块，我们总是能将这部分做到 O(\dfrac {n^2} b)。

对于块间的贡献，我们可以将原序列离散化处理。对于每个数，将其变为其属于的块。那么，我们将序列分为 b 块。显然，和散块相关的贡献都是平凡的——这里和上面的二维数点同理。

我们只需要预处理块到块之间的贡献。显然，单块内的贡献也是平凡的。对于块到块之间的贡献，我们发现一个惊人的事实：设 a_{i,j} 为块 i 中 \le j 的元素数量，b_{j,i} 为块 i 中 j+1 的数量，块 x 和块 y 的贡献就为 \sum_{i=1}^{b+1} a_{x,i}b_{i,y}。

这是一个矩阵乘法的形式。这就意味着，如果矩阵乘法的时间复杂度为 O(n^k)，那么这个算法的时间复杂度就是 O(\dfrac {n^2} b+b^k)，显然，当 b=n^{\frac 2 {k+1}} 时，算法有最优时间复杂度 O(n^{\frac {2k} {k+1}})。

取 k=2.3728596，该算法的时间复杂度为 O(n^{1.4070315})。

很遗憾，这类做法并不能做到 polylog 时间复杂度区间逆序对。