考虑如果我们把这个图建出来，那么显然会得到一张平面图。根据欧拉定理 \(V-E+F=C+1\)，只要求出 \(V,E,F\) 就能求出答案了。
\(V\) 容易求得：就是 \((x_2-x_1+2)(y_2-y_1+2)\)。
\(E\) 也不难求，就是相邻且不同的元素对数，直接二维前缀和就可以求出。
考虑怎么求 \(F\)：对于询问是整个矩形的情况，相当于封闭区域数 \(+1\)（即外边界），只要 bfs 一遍求出所有不与外边界连通的区域就行了（注意，这里的区域并不是对原矩形中的 \((i,j)\) 进行 bfs，而是对它们的交点 bfs，即如果将原矩形中的区域看作一个 \(1\times 1\) 的正方形，那么我们实际上是对正方形与正方形之间的交点 bfs）。
对于询问不是整个矩形的情况，我们还是先 bfs 预处理出所有区域，对于所有区域，随便钦定一个代表点。这样计算 \(F\) 的时候，我们先计算出矩形内部关键点个数，然后考察边界上所有点表示的区域，显然这些区域是与外界连通的，因此如果它们的代表点在里面，我们就将 \(F\) 减去 \(1\)。这样询问是 \(O(n)\) 的，可以通过。
const int MAXN=1000;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int n,m,qu,s1[MAXN+5][MAXN+5],s2[MAXN+5][MAXN+5];char s[MAXN+5][MAXN+5];
int bel[MAXN+5][MAXN+5],sf[MAXN+5][MAXN+5],cmp;pii pos[MAXN*MAXN+5];
bool in(pii p,int xl,int xr,int yl,int yr){return xl<=p.fi&&p.fi<=xr&&yl<=p.se&&p.se<=yr;}
void bfs(int x,int y){
queue<pii>q;q.push(mp(x,y));bool flg=0;
sf[x][y]++;pos[++cmp]=mp(x,y);bel[x][y]=cmp;
auto check=[&](int xl,int yl,int xr,int yr){
if(xl==xr)return s[xl][max(yl,yr)]!=s[xl+1][max(yl,yr)];
else return s[max(xl,xr)][yl]!=s[max(xl,xr)][yl+1];
};
while(!q.empty()){
pii p=q.front();q.pop();int x=p.fi,y=p.se;
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(!check(x,y,nx,ny))continue;
if(nx<1||nx>=n||ny<1||ny>=m){flg=1;continue;}
if(!bel[nx][ny])bel[nx][ny]=cmp,q.push(mp(nx,ny));
}
}
if(flg)sf[x][y]--,pos[cmp]=mp(0,0);
}
int main(){
scanf("%d%d%d",&n,&m,&qu);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)s1[i][j]=(s[i][j]!=s[i-1][j]);
for(int i=1;i<=n;i++)for(int j=2;j<=m;j++)s2[i][j]=(s[i][j]!=s[i][j-1]);
for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(!bel[i][j])bfs(i,j);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
s1[i][j]+=s1[i][j-1]+s1[i-1][j]-s1[i-1][j-1];
s2[i][j]+=s2[i][j-1]+s2[i-1][j]-s2[i-1][j-1];
sf[i][j]+=sf[i][j-1]+sf[i-1][j]-sf[i-1][j-1];
}
while(qu--){
int xl,xr,yl,yr;scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
int V=1ll*(xr-xl+2)*(yr-yl+2);
int E=((xr-xl+1)+(yr-yl+1))*2;
E+=(s2[xr][yr]-s2[xr][yl]-s2[xl-1][yr]+s2[xl-1][yl]);
E+=(s1[xr][yr]-s1[xr][yl-1]-s1[xl][yr]+s1[xl][yl-1]);
int F=sf[xr-1][yr-1]-sf[xl-1][yr-1]-sf[xr-1][yl-1]+sf[xl-1][yl-1];
static bool vis[MAXN*MAXN+5];
for(int i=yl;i<yr;i++){
if(!vis[bel[xl-1][i]])vis[bel[xl-1][i]]=1,F-=in(pos[bel[xl-1][i]],xl,xr-1,yl,yr-1);
if(!vis[bel[xr][i]])vis[bel[xr][i]]=1,F-=in(pos[bel[xr][i]],xl,xr-1,yl,yr-1);
}
for(int i=xl;i<xr;i++){
if(!vis[bel[i][yl-1]])vis[bel[i][yl-1]]=1,F-=in(pos[bel[i][yl-1]],xl,xr-1,yl,yr-1);
if(!vis[bel[i][yr]])vis[bel[i][yr]]=1,F-=in(pos[bel[i][yr]],xl,xr-1,yl,yr-1);
}
for(int i=yl;i<yr;i++)vis[bel[xl-1][i]]=vis[bel[xr][i]]=0;
for(int i=xl;i<xr;i++)vis[bel[i][yl-1]]=vis[bel[i][yr]]=0;
printf("%d\n",E-V+F+1);
}
return 0;
}