Solution网上的做法大多是扫描线 + 树状数组,我的做法也差不多,只不过写的是线段树(没他们的短)。首先可以证明的是不存在永不终止的情况,所以输出 -1 是没分的(垃圾出题人),进一步考虑下可以发现最多变色一次就会把所有点染完色了,如果我们把两个同一行或同一列的两个点看成一个线段,那么染色的点一定就是行列两条线端的交点。我们只要求线段交点个数就可以了,我们可以用线段树来完成这个问题,遇到横向的边就区间更新 +1,遇到纵向的边就单点查询。看起来有点问题是吧?由于纵向的边是一个线段,我们只能要一定纵坐标范围内的横向边,线段树是无法直接维护这个东西的,所以我们离线所有纵向的- 阅读剩余部分 -