建议看这里 Ctrl F这题。

复杂度&操作次数是有 $O(n\log ^2 n)$ 的证明。