将方格（参考题目）看作一个点，相邻的两点若颜色相同则连边，即得到一张网格图，而每次询问即求子矩形内的点导出子图对应的连通块数

注意到网格图也是平面图，根据欧拉公式有$V+F-E=1+C$（其中$V,F,E$和$C$分别为点数、块数、边数和连通块数），那么不妨去求$V,F$和$E$

显然$V=(x_{2}-x_{1}+1)(y_{2}-y_{1}+1),E$可以通过二维差分$o(1)$求出（$o(nm)$预处理）

关于$F$，将原网格图中的格子看作一个点，相邻两个格子间有边当且仅当对应的公共边在原图中不存在，由此即得到一张$(n-1)(m-1)$个点的新网格图

此时的问题类似于求$C$，但不需要考虑与矩形外有边的连通块，因此可以计算

具体的，记原图中$(x,y),(x,y+1),(x+1,y)$和$(x+1,y+1)$为顶点的方格在新图中对应的点为$(x,y)$，那么问题所求的即是新图中全部在$x\in [x_{1},x_{2}),y\in [y_{1},y_{2})$这个范围内的连通块数+1

（注意到不严格在其内部的，必然会与外界成为同一个块）

可以对每一个连通块求出包含其的极小矩形，但之后的问题并不容易处理

在每一个连通块中任选一个点，显然连通块全部在该矩形内部的必要条件为该点在矩形内部

由此，同样二维差分求出这样的连通块数，再枚举矩形更外面一圈，若该点所在的连通块对应的点在矩形内部则将其删除（重复只删除一次）

时间复杂度为$o(nm+qn+qm)$，可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 1005
 4 #define fi first
 5 #define se second
 6 #define y1 y11
 7 struct Edge{
 8     int nex,to;
 9 }edge[4*N*N];
10 pair<int,int>pos[N*N];
11 int n,m,q,V,E,F,scc,x1,y1,x2,y2,sumx[N][N],sumy[N][N],sumf[N][N],head[N*N],bl[N*N],vis[N*N];
12 char s[N][N];
13 int id(int x,int y){
14     if ((!x)||(!y)||(x==n)||(y==m))return 0;
15     return (x-1)*(m-1)+y;
16 }
17 void add(int x,int y){
18     edge[E].nex=head[x];
19     edge[E].to=y;
20     head[x]=E++;
21 }
22 void dfs(int k){
23     if (bl[k])return;
24     bl[k]=scc;
25     for(int i=head[k];i!=-1;i=edge[i].nex)dfs(edge[i].to);
26 }
27 int main(){
28     scanf("%d%d%d",&n,&m,&q);
29     for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
30     for(int i=2;i<=n;i++)
31         for(int j=1;j<=m;j++)
32             sumx[i][j]=sumx[i-1][j]+sumx[i][j-1]-sumx[i-1][j-1]+(s[i][j]==s[i-1][j]);
33     for(int i=1;i<=n;i++)
34         for(int j=2;j<=m;j++)
35             sumy[i][j]=sumy[i-1][j]+sumy[i][j-1]-sumy[i-1][j-1]+(s[i][j]==s[i][j-1]);
36     memset(head,-1,sizeof(head));
37     for(int i=0;i<n;i++)
38         for(int j=0;j<m;j++){
39             if ((j)&&(s[i+1][j]!=s[i+1][j+1])){
40                 add(id(i,j),id(i+1,j));
41                 add(id(i+1,j),id(i,j));
42             }
43             if ((i)&&(s[i][j+1]!=s[i+1][j+1])){
44                 add(id(i,j),id(i,j+1));
45                 add(id(i,j+1),id(i,j));
46             }
47         }
48     for(int i=0;i<n;i++)
49         for(int j=0;j<m;j++)
50             if (!bl[id(i,j)]){
51                 pos[++scc]=make_pair(i,j);
52                 dfs(id(i,j));
53             }
54     for(int i=1;i<=scc;i++)sumf[pos[i].fi][pos[i].se]=1;
55     sumf[0][0]=0;
56     for(int i=1;i<n;i++)
57         for(int j=1;j<m;j++)sumf[i][j]+=sumf[i-1][j]+sumf[i][j-1]-sumf[i-1][j-1];
58     for(int i=1;i<=q;i++){
59         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
60         V=(x2-x1+1)*(y2-y1+1),E=0;
61         E+=sumx[x2][y2]-sumx[x1][y2]-sumx[x2][y1-1]+sumx[x1][y1-1];
62         E+=sumy[x2][y2]-sumy[x2][y1]-sumy[x1-1][y2]+sumy[x1-1][y1];
63         x2--,y2--;
64         F=sumf[x2][y2]-sumf[x1-1][y2]-sumf[x2][y1-1]+sumf[x1-1][y1-1];
65         for(int j=y1;j<=y2;j++){
66             int k=bl[id(x1-1,j)];
67             if ((x1<=pos[k].fi)&&(pos[k].fi<=x2)&&(y1<=pos[k].se)&&(pos[k].se<=y2)&&(vis[k]!=i)){
68                 F--;
69                 vis[k]=i;
70             }
71             k=bl[id(x2+1,j)];
72             if ((x1<=pos[k].fi)&&(pos[k].fi<=x2)&&(y1<=pos[k].se)&&(pos[k].se<=y2)&&(vis[k]!=i)){
73                 F--;
74                 vis[k]=i;
75             }
76         }
77         for(int j=x1;j<=x2;j++){
78             int k=bl[id(j,y1-1)];
79             if ((x1<=pos[k].fi)&&(pos[k].fi<=x2)&&(y1<=pos[k].se)&&(pos[k].se<=y2)&&(vis[k]!=i)){
80                 F--;
81                 vis[k]=i;
82             }
83             k=bl[id(j,y2+1)];
84             if ((x1<=pos[k].fi)&&(pos[k].fi<=x2)&&(y1<=pos[k].se)&&(pos[k].se<=y2)&&(vis[k]!=i)){
85                 F--;
86                 vis[k]=i;
87             }
88         }
89         printf("%d\n",V+F-E);
90     }
91     return 0;
92 }

View Code