Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

Solution [USACO21JAN] Paint by Letters P

posted on 2021-08-19 09:18:05 | under 题解 |

由题意可知,我们要求的是一个子矩阵的连通块个数。

而由著名的平面图欧拉定理,我们有 $|V|-|E|+|F|=|C|+1$,其中 $|V|,|E|,|F|,|C|$ 分别为点集、边集、区域集和连通块集。

若除去无界域,我们的式子变为 $|V|-|E|+|F|-1=|C|$。

我们将讨论 $|V|,|E|,|F|$ 如何快速求出。

点集

显然为 $(x_2-x_1+1)(y_2-y_1+1)$。

边集

记录一个点 $(x,y)$ 向右、向下连边的个数,作一遍二位前缀和,分开查询横向和纵向的边的个数,相应地上去最后一行和最后一列即可。

有界区域集

注意到一个区域其实一个就是 $2\times 2$ 的正方形的连通块,这里的连通定义为没有横向或纵向的边阻挡。

所以我们可以 bfs 出所有的区域,并在子矩阵查询中做一些删减即可。

具体地,我们令 $(i,j)$ 代表以 $(i,j)$ 为左上角的 $2\times 2$ 正方形,向四周扩展出所有与它连通的 $2\times 2$ 正方形。

将每一个区域中的一个点标记为 1,其余点标记为 0,做一遍二维前缀和。

注意到以 $(x_1,y_1)$ 为左上角,$(x_2,y_2)$ 为右下角的子矩阵中共有 $(x_2-x_1)(y2-y_1)$ 个 $2\times 2$ 的正方形,即满足 $i\in[x_1,x_2),j\in[y_1,y_2)$ 的这些以 $(i,j)$ 为左上角的正方形。

所以我们可以先查一遍相应子矩阵的二位前缀和,再减去标记点在该子矩阵中,且扩展到子矩阵外的不同的域的个数,这个很好处理,扫一遍外围的 $2\times 2$ 的正方形即可。

总的时间复杂度为 $\mathcal O(nm+q(n+m))$。