应该是 $O(n)$ 的吧。虽然不知道它为啥这样写。

我看到是分治，好家伙，直接涂了一个 $O(n \log n)$ 上去。考后两分钟悟出来是错的。