rt，做法比题解区现有的做法更简单 + 好写 + 易懂，并且时间复杂度也是 $O(N)$。

https://www.luogu.com.cn/article/tfsgec98