RT。

https://www.luogu.com.cn/blog/250637/p3261-sol。

题解区找了一圈没找到在线且时空复杂度正确的题解。