Luogu

分析

如果我们在相邻的两个相同字符间连一条边，可以发现得到的图为平面图。

对于平面图，我们有欧拉公式

$$
F + V - E = C + 1
$$

其中 $F$ 为区域数（无界域也算一个区域）、$V$ 为点数、$E$ 为边数、$C$ 为连通块数。

于是我们可以想办法求出 $F, V, E$。

$V$ 是好求的，即为 $(x_2 - x_1 + 1)(y_2 - y_1 + 1)$；$E$ 也是好求的，只需要维护二维前缀和即可。下面考虑如何求 $F$。

首先我们可以 BFS 找到所有的区域。对于每个区域，我们给它选择一个标记点，然后二维前缀和算出矩形中标记点的个数。对于每个询问，我们遍历其边界，如果边界所属区域的标记点在询问矩形中，说明这个区域在这个询问中属于无界域，我们需要将其减去。这里注意不要重复减去某个区域。

这样子就做完了，时间复杂度 $\mathcal{O}(nm + nq + mq)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 1000 + 10;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

int n, m, Q;
char s[N][N];
int se[2][N][N], sf[N][N];
int bl[N][N], tot = 0;
std::pair<int, int> pos[N * N];
int vis[N * N];

void bfs(int sx, int sy) {
    std::queue<std::pair<int, int>> Q; Q.emplace(sx, sy);
    bl[sx][sy] = ++tot, ++sf[sx][sy], pos[tot] = std::make_pair(sx, sy);
    auto isconnected = [](int x1, int y1, int x2, int y2) -> bool {
        if (x1 == x2) return s[x1][std::max(y1, y2)] != s[x1 + 1][std::max(y1, y2)];
        else return s[std::max(x1, x2)][y1] != s[std::max(x1, x2)][y1 + 1];
    };
    int flag = 0;
    while (!Q.empty()) {
        int x = Q.front().first, y = Q.front().second; Q.pop();
        for (int d = 0; d < 4; ++d) {
            int X = x + dx[d], Y = y + dy[d];
            if (!isconnected(x, y, X, Y)) continue;
            if (X < 1 || X > n || Y < 1 || Y > m) { flag = 1; continue; }
            if (!bl[X][Y]) bl[X][Y] = tot, Q.emplace(X, Y);
        }
    }
    if (flag) --sf[sx][sy], pos[tot] = std::make_pair(0, 0);
}

int main() {
    n = read(), m = read(), Q = read();
    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (i < n && s[i][j] == s[i + 1][j]) se[0][i][j] = 1;
            if (j < m && s[i][j] == s[i][j + 1]) se[1][i][j] = 1;
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int k = 0; k < 2; ++k)
                se[k][i][j] += se[k][i - 1][j] + se[k][i][j - 1] - se[k][i - 1][j - 1];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (!bl[i][j]) bfs(i, j);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            sf[i][j] += sf[i - 1][j] + sf[i][j - 1] - sf[i - 1][j - 1];
    auto S = [](int s[][N], int lx, int ly, int rx, int ry) -> int {
        return s[rx][ry] - s[lx - 1][ry] - s[rx][ly - 1] + s[lx - 1][ly - 1];
    };
    auto in = [](int p, int lx, int ly, int rx, int ry) -> bool {
        int x = pos[p].first, y = pos[p].second;
        return lx <= x && x <= rx && ly <= y && y <= ry;
    };
    while (Q--) {
        int lx = read(), ly = read(), rx = read(), ry = read();
        int V = (rx - lx + 1) * (ry - ly + 1);
        int E = S(se[0], lx, ly, rx - 1, ry) + S(se[1], lx, ly, rx, ry - 1);
        int F = S(sf, lx, ly, rx - 1, ry - 1);
        for (int i = lx; i <= rx; ++i)
            if (!vis[bl[i][ly - 1]] && in(bl[i][ly - 1], lx, ly, rx - 1, ry - 1))
                vis[bl[i][ly - 1]] = 1, --F;
        for (int i = lx; i <= rx; ++i)
            if (!vis[bl[i][ry]] && in(bl[i][ry], lx, ly, rx - 1, ry - 1))
                vis[bl[i][ry]] = 1, --F;
        for (int i = ly; i <= ry; ++i)
            if (!vis[bl[lx - 1][i]] && in(bl[lx - 1][i], lx, ly, rx - 1, ry - 1))
                vis[bl[lx - 1][i]] = 1, --F;
        for (int i = ly; i<= ry; ++i)
            if (!vis[bl[rx][i]] && in(bl[rx][i], lx, ly, rx - 1, ry - 1))
                vis[bl[rx][i]] = 1, --F;
        printf("%d\n", V - E + F);

        for (int i = lx; i <= rx; ++i) vis[bl[i][ly - 1]] = 0;
        for (int i = lx; i <= rx; ++i) vis[bl[i][ry]] = 0;
        for (int i = ly; i <= ry; ++i) vis[bl[lx - 1][i]] = 0;
        for (int i = ly; i<= ry; ++i) vis[bl[rx][i]] = 0;
    }
    return 0;
}