矩形（rectangle）

给定 $n\times n$ 的 $01$ 矩形。$m$ 次询问，每次询问求有多少个 $a$ 行 $b$ 列的矩形满足其边上均为 $1$。

$n,m\le 1500$，时限 $5s$。

首先套路性的求出 $r_{i,j}$ 表示 $(i,j)$ 右边最长可以延伸的长度，$d_{i,j}$ 表示 $(i,j)$ 下面最长可以延伸的长度。

然后一个矩形 $(i,j)(i+a-1,j+b-1)$ 合法当且仅当：

$$[r_{i,j}\ge b][d_{i,j}\ge a][d_{i,j+b-1}\ge a][r_{i+a-1,j}\ge b]$$

这是一个偏序问题，可以使用 bitset 解决。

不妨设 bitset $R_{i,j,k},D_{i,j,k}$ 表示 $[r_{i,j}\ge k],[d_{i,j}\ge k]$，那么根据我们精湛的 bitset 技术，可得答案需要枚举行数 $i$，然后累加：

for(int j=1;j+a-1<=n;j++)
    ans+=(D[j][a]&(D[j][a]>>b-1)&R[j][b]&R[j+a-1][b]).count();

这样做时间复杂度 $\mathcal{O}(\frac{n^3}{\omega})$，空间复杂度 $\mathcal{O}(\frac{n^3}{\omega})$。这样空间会爆掉。

考虑经典 bitset trick：离线询问。

不妨将所有询问离线下来，然后考虑扫描线，不存储 $R,D$ 的最后一维：设当前扫描线到 $k$，则 $R_{i,j}=[r_{i,j}\ge k],D_{i,j}=[d_{i,j}\ge k]$。

那这样空间复杂度就是 $\mathcal{O}(\frac{n^2}{\omega})$ 的了。

那么我们只要考虑记录所有询问的每一行的 bitset 是谁，然后每次一旦扫到 $a$ 或者 $b$，可以直接将其 $\land$ 到对应行的 bitset 上。

具体代码：

bitset<N>R[N],ans[N][N];
vector<int>va[N],vb[N];
vector<pii>vr[N],vd[N];
void solve(int m){
    for(int i=1;i<=n;i++)va[i].clear(),vb[i].clear();
    for(int i=1,a,b;i<=m;i++){
        scanf("%d%d",&a,&b);
        for(int j=1;j<=n;j++)ans[j][i].reset();
        va[a].push_back(i),vb[b].push_back(i);
        A[i]=a,B[i]=b;
    }
    for(int i=1;i<=n;i++)R[i].reset();
    for(int i=n;i>=1;i--){
        for(pii k:vr[i])
            R[k.first][k.second]=1;
        for(int k:vb[i])
            for(int j=1;j<=n;j++)
                ans[j][k]=R[j]&R[j+A[k]-1];
    }
    for(int i=1;i<=n;i++)R[i].reset();
    for(int i=n;i>=1;i--){
        for(pii k:vd[i])
            R[k.first][k.second]=1;
        for(int k:va[i])
            for(int j=1;j<=n;j++)
                ans[j][k]&=R[j]&(R[j]>>B[k]-1);
    }
    for(int i=1;i<=m;i++){
        int cnt=0;
        for(int j=1;j<=n;j++)
            cnt+=ans[j][i].count();
        printf("%d\n",cnt);
    }
}

然后此时你就会发现一个问题：空间还是 $\mathcal{O}(\frac{n^2m}{\omega})$。

接下来考虑经典 bitset trick：分组询问。

具体的，将询问分为 $B$ 组，对每一组内部分别离线询问，则空间复杂度 $\mathcal{O}(\frac{n^2B}{\omega})$。但这样空间复杂度会变化：$\mathcal{O}(\frac{Bn^3+n^2m}{\omega})$。

于是取一个 $B=15$ 即可。

#include <bits/stdc++.h>
using namespace std;
const int N=1510;
using pii=pair<int,int>;
int n,m,a[N][N],r[N][N],d[N][N],A[N],B[N];
bitset<N>R[N],ans[N][110];
vector<int>va[N],vb[N];
vector<pii>vr[N],vd[N];
void solve(int m){
    for(int i=1;i<=n;i++)va[i].clear(),vb[i].clear();
    for(int i=1,a,b;i<=m;i++){
        scanf("%d%d",&a,&b);
        for(int j=1;j<=n;j++)ans[j][i].reset();
        va[a].push_back(i),vb[b].push_back(i);
        A[i]=a,B[i]=b;
    }
    for(int i=1;i<=n;i++)R[i].reset();
    for(int i=n;i>=1;i--){
        for(pii k:vr[i])
            R[k.first][k.second]=1;
        for(int k:vb[i])
            for(int j=1;j<=n;j++)
                ans[j][k]=R[j]&R[j+A[k]-1];
    }
    for(int i=1;i<=n;i++)R[i].reset();
    for(int i=n;i>=1;i--){
        for(pii k:vd[i])
            R[k.first][k.second]=1;
        for(int k:va[i])
            for(int j=1;j<=n;j++)
                ans[j][k]&=R[j]&(R[j]>>B[k]-1);
    }
    for(int i=1;i<=m;i++){
        int cnt=0;
        for(int j=1;j<=n;j++)
            cnt+=ans[j][i].count();
        printf("%d\n",cnt);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
        scanf("%1d",&a[i][j]);
    for(int i=1;i<=n;i++)for(int j=n;j>=1;j--)
        if(a[i][j]==0)r[i][j]=0;
        else r[i][j]=r[i][j+1]+1;
    for(int j=1;j<=n;j++)for(int i=n;i>=1;i--)
        if(a[i][j]==0)d[i][j]=0;
        else d[i][j]=d[i+1][j]+1;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
        vr[r[i][j]].push_back({i,j}),vd[d[i][j]].push_back({i,j});
    int sum=0;
    for(int i=1;i<=14;i++)sum+=(m/15),solve(m/15);
    solve(m-sum);
    return 0;
}

一个以 $(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;
}