考虑欧拉平面图公式：$|V|-|E|+|F|=k+1$。其中 $k$ 是连通块个数。

按照如下方式建图，边和点如图所示：

对于每个询问，还需要加上询问的矩形外围的一圈边：

答案即为 $|F|-1=|E|-|V|+k$。$|V|$ 容易计算。 $|E|$ 直接二维前缀和。重点在计算 $k$ 上。

除去一个红色边所在的大连通块，问题变成了计算完全在红框内部（不包含边界）的连通块数量。

方法 1

搜出所有连通块（注意不是颜色块），记录其上下左右边界，问题转化成离线四维数点，两层 cdq 分治即可。

但是发现这样会 TLE，因为搜连通块时加入了大量无用的孤点，特判掉并加一个二位前缀和即可。 ::::success[Code]

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define il inline
#define x1 vjhgof
#define y1 asdfas
#define x2 tywtgr
#define y2 rtfjkl
using namespace std;
constexpr int N=1001,M=N*N,INF=1e9;
struct Comp{
    bool tp;
    int x1,y1,x2,y2,id;
    bool mk;
}a[M],b[M];
int n,m,q,cnt;
int r[N][N],d[N][N],f[N][N],ans[N],bit[N];
char s[N][N];
bool vis[N][N];
il void add(int p,int x){while(p<=m+1) bit[p]+=x,p+=p&-p;}
il int ask(int p){int res=0;while(p>0) res+=bit[p],p&=p-1;return res;}
il bool cmp1(const Comp &a,const Comp &b){return a.x1==b.x1?a.tp<b.tp:a.x1>b.x1;}
il bool cmp2(const Comp &a,const Comp &b){return a.y1==b.y1?a.tp<b.tp:a.y1>b.y1;}
il bool cmp3(const Comp &a,const Comp &b){return a.x2==b.x2?a.tp<b.tp:a.x2<b.x2;}
void dfs(int i,int j,int id){
    vis[i][j]=true;
    a[id].x1=min(a[id].x1,i),a[id].y1=min(a[id].y1,j);
    a[id].x2=max(a[id].x2,i),a[id].y2=max(a[id].y2,j);
    if(r[i][j]&&!vis[i][j+1]) dfs(i,j+1,id);
    if(d[i][j]&&!vis[i+1][j]) dfs(i+1,j,id);
    if(j&&r[i][j-1]&&!vis[i][j-1]) dfs(i,j-1,id);
    if(i&&d[i-1][j]&&!vis[i-1][j]) dfs(i-1,j,id);
}
void cdq2(int l,int r){
    if(l==r) return;
    int mid=l+r>>1,i=l,j=mid+1,k=l;
    cdq2(l,mid);
    cdq2(mid+1,r);
    while(i<=mid&&j<=r){
        if(cmp3(a[i],a[j])){
            if(!a[i].mk&&!a[i].tp) add(a[i].y2,1);
            b[k++]=a[i++];
        }else{
            if(a[j].mk&&a[j].tp) ans[a[j].id]+=ask(a[j].y2);
            b[k++]=a[j++];
        }
    }
    while(j<=r){
        if(a[j].mk&&a[j].tp) ans[a[j].id]+=ask(a[j].y2);
        b[k++]=a[j++];
    }
    rept(i2,l,i-1) if(!a[i2].mk&&!a[i2].tp) add(a[i2].y2,-1);
    while(i<=mid) b[k++]=a[i++];
    rept(i,l,r) a[i]=b[i];
}
void cdq1(int l,int r){
    if(l==r) return;
    int mid=l+r>>1,i=l,j=mid+1,k=l;
    cdq1(l,mid);
    cdq1(mid+1,r);
    rept(i,l,mid) a[i].mk=false;
    rept(i,mid+1,r) a[i].mk=true;
    while(i<=mid&&j<=r) cmp2(a[i],a[j])?b[k++]=a[i++]:b[k++]=a[j++];
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    rept(i,l,r) a[i]=b[i];
    cdq2(l,r);
    sort(a+l,a+r+1,cmp2);
}
signed main(){
    scanf("%d%d%d",&n,&m,&q);
    rept(i,1,n) scanf("%s",s[i]+1);
    rep(i,1,n) rep(j,0,m) r[i][j]=s[i][j+1]!=s[i+1][j+1];
    rep(i,0,n) rep(j,1,m) d[i][j]=s[i+1][j]!=s[i+1][j+1];
    rept(i,0,n){
        rept(j,0,m){
            if(!vis[i][j]){
                a[++cnt]={0,INF,INF,-INF,-INF,0,0};
                dfs(i,j,cnt);
                if(a[cnt].x1==a[cnt].x2&&a[cnt].y1==a[cnt].y2) ++f[i][j],--cnt;
            }
        }
    }
    rept(i,1,n) r[i][0]+=r[i-1][0],d[i][0]+=d[i-1][0],f[i][0]+=f[i-1][0];
    rept(j,1,m) r[0][j]+=r[0][j-1],d[0][j]+=d[0][j-1],f[0][j]+=f[0][j-1];
    rept(i,1,n){
        rept(j,1,m){
            r[i][j]+=r[i-1][j]+r[i][j-1]-r[i-1][j-1];
            d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
            f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
        }
    }
    rept(i,1,q){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2),--x1,--y1;
        int V=(x2-x1+1)*(y2-y1+1),E=(x2-x1+y2-y1)<<1;
        E+=d[x2-1][y2-1]-(!x1?0:d[x1-1][y2-1])-d[x2-1][y1]+(!x1?0:d[x1-1][y1]);
        E+=r[x2-1][y2-1]-(!y1?0:r[x2-1][y1-1])-r[x1][y2-1]+(!y1?0:r[x1][y1-1]);
        a[++cnt]={1,x1+1,y1+1,x2-1,y2-1,i,0};
        ans[i]=E-V+f[x2-1][y2-1]-f[x1][y2-1]-f[x2-1][y1]+f[x1][y1]+1;
    }
    sort(a+1,a+cnt+1,cmp1);
    rept(i,1,cnt) ++a[i].y2;
    cdq1(1,cnt);
    rept(i,1,q) printf("%d\n",ans[i]);
    return 0;
}

::::

方法 2

经典技巧：对于每个连通块，选取任意一个节点作为其代表节点。只需要统计落在询问边界内的代表节点数，减去其中不完全在边界内的连通块数。

发现不完全在边界内的连通块必然穿过边界。沿着边界扫一遍即可。 ::::success[Code]

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define il inline
#define x1 vjhgof
#define y1 asdfas
#define x2 tywtgr
#define y2 rtfjkl
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
constexpr int N=1001;
int n,m,q,cnt;
int r[N][N],d[N][N],f[N][N];
pii mk[N][N];
char s[N][N];
bool vis[N][N];
set<pii> st;
void dfs(int i,int j,pii id){
    vis[i][j]=true;
    mk[i][j]=id;
    if(r[i][j]&&!vis[i][j+1]) dfs(i,j+1,id);
    if(d[i][j]&&!vis[i+1][j]) dfs(i+1,j,id);
    if(j&&r[i][j-1]&&!vis[i][j-1]) dfs(i,j-1,id);
    if(i&&d[i-1][j]&&!vis[i-1][j]) dfs(i-1,j,id);
}
signed main(){
    scanf("%d%d%d",&n,&m,&q);
    rept(i,1,n) scanf("%s",s[i]+1);
    rep(i,1,n) rep(j,0,m) r[i][j]=s[i][j+1]!=s[i+1][j+1];
    rep(i,0,n) rep(j,1,m) d[i][j]=s[i+1][j]!=s[i+1][j+1];
    rept(i,0,n){
        rept(j,0,m){
            if(!vis[i][j]){
                ++f[i][j];
                dfs(i,j,{i,j});
            }
        }
    }
    rept(i,1,n) r[i][0]+=r[i-1][0],d[i][0]+=d[i-1][0],f[i][0]+=f[i-1][0];
    rept(j,1,m) r[0][j]+=r[0][j-1],d[0][j]+=d[0][j-1],f[0][j]+=f[0][j-1];
    rept(i,1,n){
        rept(j,1,m){
            r[i][j]+=r[i-1][j]+r[i][j-1]-r[i-1][j-1];
            d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
            f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
        }
    }
    rept(i,1,q){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2),--x1,--y1;
        int V=(x2-x1+1)*(y2-y1+1),E=(x2-x1+y2-y1)<<1,K=1;
        st.clear();
        E+=d[x2-1][y2-1]-(!x1?0:d[x1-1][y2-1])-d[x2-1][y1]+(!x1?0:d[x1-1][y1]);
        E+=r[x2-1][y2-1]-(!y1?0:r[x2-1][y1-1])-r[x1][y2-1]+(!y1?0:r[x1][y1-1]);
        K+=f[x2-1][y2-1]-f[x1][y2-1]-f[x2-1][y1]+f[x1][y1];
        auto check=[x1,y1,x2,y2](pii p)->bool{
            if(p.fi<=x1||p.fi>=x2||p.se<=y1||p.se>=y2) return false;
            if(st.count(p)) return false;
            return st.emplace(p),true;
        };
        rept(i,x1,x2){
            K-=check(mk[i][y1]);
            K-=check(mk[i][y2]);
        }
        rept(j,y1+1,y2-1){
            K-=check(mk[x1][j]);
            K-=check(mk[x2][j]);
        }
        printf("%d\n",E-V+K);
    }
    return 0;
}

::::