这道题其实是 P4198 楼房重建 的加强版，P4198 是紫，这题是蓝，而且 $O(n^2q)$ 可以卡过去。

建议 P4198 降蓝，然后本题时限改为 3s，卡掉暴力做法