rt，模拟赛上出了本题的 $O(n)$ 强化版且有许多人场切，个人认为 $O(nS)$ 做法只有绿题水平。