一个以 $(i,j)$ 为左上角的 $a$ 行 $b$ 列矩形，四条边全黑等价于四个「连续黑格段」条件同时成立：

• 上边：从 $(i,j)$ 往右连续 $b$ 个格子是黑的；
• 下边：从 $(i+a-1,j)$ 往右连续 $b$ 个格子是黑的；
• 左边：从 $(i,j)$ 往下连续 $a$ 个格子是黑的；
• 右边：从 $(i,j+b-1)$ 往下连续 $a$ 个格子是黑的。

预处理。对每个格子算出两个量：向右的黑色连续长度、向下的黑色连续长度。把「向右连续长度恰好为 $p$」的格子塞进桶 row[p]、「向下连续长度恰好为 $p$」的格子塞进桶 col[p]，并做前缀和。这样「连续长度 $\ge p$」的格子就是若干个桶的并，改动一个阈值只需要动两段桶，差量可以承受。

回答询问。用两组 bitset 记录「当前阈值下，每个格子是否满足上/下边条件和左/右边条件」：

• r[i] 的第 $j$ 位表示 $(i,j)$ 的向右连续长度达到当前阈值；
• c[i] 的第 $j$ 位表示 $(i,j)$ 的向下连续长度达到当前阈值。

对询问 $(a,b)$，把 c 的阈值调成与 $a$、r 的阈值调成与 $b$ 匹配（只改两次询问之间的差量），然后逐个 $i$ 用

(c[i] & c[i + a - 1] & r[i] & (r[i] >> (b - 1))).count()

一次数出所有合法的左上角：

• & c[i + a - 1] ：用 $a$ 行的位移把「左边」搬到「上下两条边」。

• >> (b - 1) ：用 $b$ 列的位移把「上边」搬到「左边」。

按位与下来剩下的位就是同时满足四个条件的左上角。

bitset 的位运算是 $O(n/64)$ 的，所以每组询问只需 $O(n^2/64)$。

可以把询问按「与上一次询问的阈值差之和最小」的顺序处理，把 bitset 的置位/清位总量压下来。

具体结合代码理解。

#include <cstdio>
#include <cstring>
#include <vector>
#include <bitset>
using namespace std;

#define N 1505
#define PII pair<int, int>

int n, m;
int g[N][N];
char s[N];
int row[N], col[N];       // 桶的前缀和（估改动阈值的代价）
vector<PII> pr[N], pc[N]; // 向右 / 向下连续长度恰好为 p 的格子
bitset<N> r[N], c[N];     // 当前阈值下，每行哪些格子满足条件
int qa[N], qb[N], vis[N];
int a, b; // 当前 bitset 对应的阈值
int ans[N];

int dis(int u) {
    return abs(row[a] - row[qa[u]]) + abs(col[b] - col[qb[u]]);
}

int count() { // 数所有合法的 a × b 左上角
    int res = 0;
    for (int i = 0; i + a - 1 < n; i++) {
        res += (r[i] & r[i + a - 1] & c[i] & (c[i] >> (b - 1))).count();
    }
    return res;
}

int main() {
    // freopen("rectangle.in", "r", stdin);
    // freopen("rectangle.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        for (int j = 0; j < n; j++) {
            g[i][j] = s[j] - '0';
        }
    }
    for (int i = 0; i < n; i++) { // 每个格子向右的连续长度
        int cnt = 0;
        for (int j = n - 1; j >= 0; j--) {
            cnt = g[i][j] ? cnt + 1 : 0;
            if (cnt) pr[cnt].push_back(make_pair(i, j));
        }
    }
    for (int j = 0; j < n; j++) { // 每个格子向下的连续长度
        int cnt = 0;
        for (int i = n - 1; i >= 0; i--) {
            cnt = g[i][j] ? cnt + 1 : 0;
            if (cnt) pc[cnt].push_back(make_pair(i, j));
        }
    }
    for (int i = 1; i <= n; i++) {
        row[i] = row[i - 1] + pr[i].size();
        col[i] = col[i - 1] + pc[i].size();
    }
    for (int i = 0; i < m; i++) scanf("%d %d", &qa[i], &qb[i]);
    for (int i = 0; i < n; i++) { // 初始阈值是 1，所有黑格都满足
        for (int j = 0; j < n; j++) {
            if (g[i][j]) {
                r[i][j] = 1;
                c[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        int val = 1 << 30, pos = -1;
        for (int j = 0; j < m; j++) {
            if (vis[j]) continue;
            int d = dis(j);
            if (d < val) {
                val = d;
                pos = j;
            }
        }
        if (a <= qa[pos]) {
            for (int p = a; p < qa[pos]; p++) {
                for (PII x : pc[p]) {
                    c[x.first][x.second] = 0;
                }
            }
        } else {
            for (int p = qa[pos]; p < a; p++) {
                for (PII x : pc[p]) {
                    c[x.first][x.second] = 1;
                }
            }
        }
        if (b <= qb[pos]) {
            for (int p = b; p < qb[pos]; p++) {
                for (PII x : pr[p]) {
                    r[x.first][x.second] = 0;
                }
            }
        } else {
            for (int p = qb[pos]; p < b; p++) {
                for (PII x : pr[p]) {
                    r[x.first][x.second] = 1;
                }
            }
        }
        a = qa[pos];
        b = qb[pos];
        vis[pos] = 1;
        ans[pos] = count();
    }
    for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
    return 0;
}