洛谷 P7295 [USACO21JAN] Paint by Letters P 题解

Solution

考虑欧拉平面图公式：\(|V|-|E|+|F|=k+1\)。其中 \(k\) 是连通块个数。
按照如下方式建图，边和点如图所示：

对于每个询问，还需要加上询问的矩形外围的一圈边：

答案即为 \(|F|-1=|E|-|V|+k\)。\(|V|\) 容易计算。 \(|E|\) 直接二维前缀和。重点在计算 \(k\) 上。
除去一个红色边所在的大连通块，问题变成了计算完全在红框内部（不包含边界）的连通块数量。
那么直接建出图后搜出所有连通块（注意不是颜色块），记录其上下左右边界 \(x_1,y_1,x_2,y_2\)，将问题转化成离线四维数点，两层 cdq 分治即可。
但是发现这样会 TLE，因为搜连通块时加入了大量无用的孤点，特判掉并加一个二位前缀和即可。然后跑得飞快，目前最优解。
Code

[code]#include #define rep(i,a,b) for(int i(a);i

懂技术并乐意极积无私分享的人越来越少。珍惜

喜欢鼓捣这些软件，现在用得少，谢谢分享！