题解

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n,m,q,E[2][N][N],mx[N][N],my[N][N],F[N][N];
char s[N][N];bool v[N][N];
bool edg(int x,int y,int zx,int zy){
if(zx<0||zy<0||zx>n||zy>m)return 0;
if(zx>0&&zx<n&&zyy+1)return (s[x][y+1]!=s[x+1][y+1]);
if(zx>0&&zx<n&&zyy-1)return (s[x][y]!=s[x+1][y]);
if(zy>0&&zy<m&&zxx+1)return (s[x+1][y]!=s[x+1][y+1]);
if(zy>0&&zy<m&&zxx-1)return (s[x][y]!=s[x][y+1]);
return 1;
}
void dfs(int x,int y){
if(x1&&y4)
x++,x--;
if(v[x][y])return;v[x][y]=1;
for(int k=0;k<4;k++){
int zx=x+dx[k],zy=y+dy[k];
if(edg(x,y,zx,zy)){
mx[zx][zy]=mx[x][y];
my[zx][zy]=my[x][y];
dfs(zx,zy);
}
}
return;
}
#define Get(F,x1,y1,x2,y2) (F[x2][y2]-((x1)?F[x1-1][y2]:0)-((y1)?F[x2][y1-1]:0)+(((x1)&&(y1))?F[x1-1][y1-1]:0))
int check(int x,int y,int x1,int y1,int x2,int y2){
if(!v[x][y]&&x>=x1&&x<=x2&&y>=y1&&y<=y2)
{v[x][y]=1;return 1;}
return 0;
}
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
cin>>s[i]+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
E[0][i][j]=E[0][i-1][j]+E[0][i][j-1]-E[0][i-1][j-1];
E[1][i][j]=E[1][i-1][j]+E[1][i][j-1]-E[1][i-1][j-1];
if(s[i][j]==s[i][j+1])E[0][i][j];
if(s[i][j]==s[i+1][j])E[1][i][j];
}
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(!v[i][j]){
mx[i][j]=i;my[i][j]=j;
F[i][j];dfs(i,j);
}
for(int i=0;i<=n;i)
for(int j=0;j<=m;j++)
F[i][j]+=(i?F[i-1][j]:0)+(j?F[i][j-1]:0)-((i&&j)?F[i-1][j-1]:0);
memset(v,0,sizeof(v));
while(q--){
int x1,y1,x2,y2,ans=0;
cin>>x1>>y1>>x2>>y2;
ans+=(x2-x1+1)*(y2-y1+1);
if(y1!=y2)ans-=Get(E[0],x1,y1,x2,y2-1);
if(x1!=x2)ans-=Get(E[1],x1,y1,x2-1,y2);
x1--;y1--;ans+=Get(F,x1,y1,x2,y2);
for(int i=x1;i<=x2;i++){
ans-=check(mx[i][y1],my[i][y1],x1,y1,x2,y2);
ans-=check(mx[i][y2],my[i][y2],x1,y1,x2,y2);
}
for(int i=y1;i<=y2;i++){
ans-=check(mx[x1][i],my[x1][i],x1,y1,x2,y2);
ans-=check(mx[x2][i],my[x2][i],x1,y1,x2,y2);
}
cout<<ans<<'\n';
for(int i=x1;i<=x2;i++){
v[mx[i][y1]][my[i][y1]]=0;
v[mx[i][y2]][my[i][y2]]=0;
}
for(int i=y1;i<=y2;i++){
v[mx[x1][i]][my[x1][i]]=0;
v[mx[x2][i]][my[x2][i]]=0;
}
}
return 0;
}