题解
树有什么性质？
如果每个蓝色连通块都是树，那么连通块个数=总点数?总
边数。
二维前缀和维护点数和边数。
\(O(nm + q)\)
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 2010
using namespace std;
int n,m,q;
int a[N][N];
int b[N][N],c[N][N];
char s[7007];
inline int calc(int a[N][N],int x1,int y1,int x2,int y2){
if(x1>x2||y1>y2) return 0;
return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}
int main() {
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) {
scanf("%s",s+1);
for(int j=1;j<=m;j++)
a[i][j]=s[j]-'0';
}
for(int i=2;i<=n;i++)
for(int j=1;j<=m;j++)
b[i][j]=a[i][j]&a[i-1][j];
for(int i=1;i<=n;i++)
for(int j=2;j<=m;j++)
c[i][j]=a[i][j]&a[i][j-1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
c[i][j]=c[i][j]+c[i-1][j]+c[i][j-1]-c[i-1][j-1];
}
while(q--) {
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",calc(a,x1,y1,x2,y2)-calc(b,x1+1,y1,x2,y2)-calc(c,x1,y1+1,x2,y2));
}
return 0;
}