题目描述

难度分:$2241$

输入$n(1 \leq n \leq 2000)$、$m(1 \leq m \leq 2000)$、$q(1 \leq q \leq 2 \times 10^5)$和一个$n$行$m$列的01网格图$c$。

其中0表示白色格子，1表示蓝色格子。保证每个由蓝色格子构成的（四方向）连通块都是树。

然后输入$q$个询问，每个询问输入$4$个数，表示一个子矩形的左上角行列坐标和右下角行列坐标（下标从$1$开始）。输出这个子矩形中，有多少个蓝色连通块。

输入样例$1$

3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4

输出样例$1$

3
2
2
2

输入样例$2$

5 5 6
11010
01110
10101
11101
01010
1 1 5 5
1 2 4 5
2 3 3 4
3 3 3 3
3 1 3 5
1 1 3 4

输出样例$2$

3
2
1
1
3
2

算法

二维前缀和

这道题的思维难度还是比较高的，但如果想到了就很容易做，只能说不愧是$AGC$的题。首先要理解连通块都是“树”的含义，即任意两个相邻的1，只有唯一一条路径连接。这样一来，对于每个询问的矩形范围内，也都是若干“树”型连通块。

那么树有一个非常关键的性质，即节点的数量$=$边的数量$+1$。只要知道被询问的子矩阵中有多少个节点以及多少条边，两者一减就是树的个数。因此构建$3$个二维前缀和数组$ns$、$vs$、$hs$分别记录以$(1,1)$为左上角的子矩阵中节点的数目、竖边的数目、横边的数目。这样每条询问都可以$O(1)$求出答案，处理完全部$q$条询问的时间复杂度为$O(q)$。

复杂度分析

时间复杂度

遍历一遍$c$矩阵预处理出$ns$、$vs$、$hs$三个前缀和矩阵，时间复杂度为$O(n^2)$。接下来每条询问$O(1)$就可以出答案，所以处理完所有询问的时间复杂度为$O(q)$。因此，整个算法的时间复杂度为$O(n^2+q)$。

空间复杂度

三个前缀和矩阵都是$O(n^2)$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 2010;
char c[N][N];
int n, m, q, ns[N][N], vs[N][N], hs[N][N];

int get(int x1, int y1, int x2, int y2) {
    int node_cnt = ns[x2][y2] - ns[x1 - 1][y2] - ns[x2][y1 - 1] + ns[x1 - 1][y1 - 1];
    int edge_vcnt = vs[x2][y2] + vs[x1][y1 - 1] - vs[x2][y1 - 1] - vs[x1][y2];
    int edge_hcnt = hs[x2][y2] + hs[x1 - 1][y1] - hs[x2][y1] - hs[x1 - 1][y2];
    return node_cnt - edge_vcnt - edge_hcnt;
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    memset(ns, 0, sizeof(ns));
    memset(vs, 0, sizeof(vs));
    memset(hs, 0, sizeof(hs));
    for(int i = 1; i <= n; i++) {
        scanf("%s", c[i] + 1);
        for(int j = 1; j <= m; j++) {
            ns[i][j] = (c[i][j] - '0') + ns[i - 1][j] + ns[i][j - 1] - ns[i - 1][j - 1];
            if(c[i][j] == '1') {
                if(c[i - 1][j] == '1') {
                    vs[i][j]++;
                }
                if(c[i][j - 1] == '1') {
                    hs[i][j]++;
                }
            }
            vs[i][j] += vs[i - 1][j] + vs[i][j - 1] - vs[i - 1][j - 1];
            hs[i][j] += hs[i - 1][j] + hs[i][j - 1] - hs[i - 1][j - 1];
        }
    }
    while(q--) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", get(x1, y1, x2, y2));
    }
    return 0;
}