给出一个 n 行 m 列的 01 矩阵。有 q 次操作，每次操作选取一个子矩阵，将子矩阵变为全 1，每次操作后输出当前连通块个数，（上下左右算联通）。 n, m < 1e4; q < 3e4.
首先，只有发生 0->1 的格子，才会导致连通块数目变化。也就是说，对于每次操作只关注子矩阵里原本是 0 的格子，（0 的格子会不断减小）
当原本是 0 的格子变为 1，连通块数目 + 1，然后分别遍历上下左右四个位置，如果遍历到的位置为 1，且之前没有在一个连通块，那么现在就将他们并入一个集合，同时连通块数目 - 1。
实现方面，可以在每一行开一个并查集，并查集的祖先表示右边第一个 0 的位置（包括本身），这样在遍历子矩阵时，只需要一行一行的找 0 的位置即可。
而判断两个 1 位置是否在一个联通块，可以用一个并查集维护，做法是将每个二维点都打上标号。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second const int INF = 0x3f3f3f3f; const int N = 1e3 + 10; int t, n, m, q, ans; char arr[N][N]; int fa[N][N], dsu[N*N]; int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; inline int find(int fa[], int x){ //在第 i 行并查集 return fa[x] = fa[x] == x ? fa[x] : find(fa, fa[x]); } inline int id(int x, int y){ // 对二维点打标号 return x * m + y; } void light(int x, int y){ // 像四个方向找 ‘1’，将两个点并入集合 arr[x][y] = '1'; ans++; // 0 -> 1，连通块数目 + 1 fa[x][y] = y + 1; for (int i = 0; i < 4; i++){ // 四个方向 int tx = x + dir[i][0], ty = y + dir[i][1]; if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && arr[tx][ty] == '1' && find(dsu, id(x, y)) != find(dsu, id(tx, ty))){ dsu[find(dsu, id(x, y))] = find(dsu, id(tx, ty)); // 如果两个点不是同一个集合 ans--; // 并入同一个集合，联通数目减一 } } } int main(){ scanf("%d%d", &n, &m); ans = 0; for (int i = 1; i <= n; i++){ scanf("%s", arr[i] + 1); for (int j = 1; j <= m; j++){ fa[i][j] = j, dsu[id(i, j)] = id(i, j); } fa[i][m + 1] = m + 1; } for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ if(arr[i][j] == '1') light(i, j); } } scanf("%d", &q); while(q--){ int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); for (int i = a; i <= c; i++){ // 找每一行 0 的位置 int s = find(fa[i], b); while(s <= d){ light(i, s); s = find(fa[i], b); } } printf("%d\n", ans); } return 0; } /* 5 6 101010 000001 101010 000001 101010 3 1 2 5 2 4 4 4 4 1 3 3 6 */