$O(n \sqrt{n})$ 过不了 $5 \times 10^5$。

别问我怎么知道的。