RT，一个可能可以启发其他题目的做法，复杂度 $\mathcal O(n\log^2 n+\frac{np}{w}\log n)$，题解里面没有。

link。