rt，点分治+单调队列按秩合并，隔壁都有黑，这题还要处理颜色、不同子树等复杂情况，难度严格大于上面那题。

至于线段树写法，上面那题也有人用线段树 $3$ 个 $\log$ 卡常过了，但一道题的难道应该是理论最优正解的复杂度吧？