kal0rona 越来越 sb了。
kal0rona 越来越 sb了。
正好在《组合数学》上看过一个结论：反图形成的连通块的点在原图一定处处连通。证明很简单：考虑点对\((u, v)\)，如果点对之间在反图中不连通显然是在原图联通的；如果在反图中连通，有一个不在当前点集的点使得他们连通。所以，我们只需要构建反图，根据「不与本点相连的点都在本连通块内」进行 BFS 即可。
看一眼复杂度，\(O(nm)\)级别的，考虑两个循环的 DP。分析整个题面之后发现，我们穿过边界时，当且仅当另一个连通块的权值比当前的大，否则便不会为了穿过边界而损失当前金块。所以，我们做一个 DP 一样的东西：因为发现每个格子只能走一遍，那么在每一列你只能选择一直向上走和一直向下走，所以这个 DP 便没了后效性，然后再处理连通块之间的连接判断就做完了。
可以把整个思路转换为 CDQ 分治下的二位数点。\(x\)轴就代表正常的物理距离的轴，然后\(y\)轴就代表信号接收的轴，把一个询问拆掉成为容斥的形式即可。
这道题好有意思啊，提醒我在任何时候都要想到这种阈值+\(0/1\)转化的方式。
我们可以先二分出\(c\)位置的值，然后令所有大于等于\(c\)的值变成\(1\)，小于的则变成\(0\)。然后排序的时候发现，其实就是重新组织零一的位置，所以用线段树区间修改就可以搞定了。最后判断\(c\)位是否为\(0/1\)决定要不要继续二分。