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

而由著名的平面图欧拉定理，我们有 $|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))$。