rt，题解区中存在 $\mathcal{O}(n^2)$ 的错解但是放过去了。还存在一车随机化解法，如

https://www.luogu.com.cn/record/169593506

https://www.luogu.com.cn/record/169592593

https://www.luogu.com.cn/record/169274452

甚至跑的比正解还快。