我的算法是 $O(n)$ 的，思路和 P5073 的思路差不多。

代码有点长，放二楼。