矩形（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;
}