【Codeforces 364E】Empty Rectangles | Mrsrz's blog

二维分治。

题目大意：

给定一个 $n\times m$ 的 01 矩阵，问有多少子矩阵的和为 $k$。

$k$ 非常小。

题解：

考虑分治。假定 $n$ 与 $m$ 同阶。

我们取一条横切当前矩阵的线，并且满足两半的大小相差最小。

然后分别考虑上、下两个部分。我们对于左端点在 $l$，右端点在 $r$ 的所有情况，求出其中一条边紧靠切割线的矩形中，矩形内部和不超过 $0\sim k$ 的矩形个数。

枚举 $l,r,k$，时间复杂度为 $O(n^2k)$。

在 $l$ 固定时，随着 $r$ 的增大，矩形的另外一个边界必然会不断往中间那条线靠近。于是可以用一个指针来搞。

这样单层分治的复杂度就是 $O(n^2k)$。

由于有两个维度，所以我们每次取长度较大的那个维度进行切割，即可保证复杂度（也可以横一刀纵一刀切）。

时间复杂度 $O(n^2k\log n)$。

Code：

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=2555;
int n,m,k,s[N][N];
char b[N][N];
LL ans;
inline int sum(int r1,int r2,int c1,int c2){
    return s[r2][c2]-s[r2][c1-1]-s[r1-1][c2]+s[r1-1][c1-1];
}
int A[N][N][7],B[N][N][7];
void solve(int l,int r,int L,int R){
    if(l==r&&L==R){
        ans+=k==(b[l][L]^'0');
        return;
    }
    if(r-l+1>R-L+1){
        const int mid=l+r>>1;
        for(int i=L;i<=R;++i)for(int j=i;j<=R;++j)memset(A[i][j],0,sizeof**A),memset(B[i][j],0,sizeof**B);
        for(int K=0;K<=k;++K){
            for(int x=L;x<=R;++x){
                int up=l,down=r;
                for(int y=x;y<=R;++y){
                    while(up<=mid&&sum(up,mid,x,y)>K)++up;
                    while(down>mid&&sum(mid+1,down,x,y)>K)--down;
                    A[x][y][K]=mid-up+1,B[x][y][K]=down-mid;
                }
            }
        }
        for(int x=L;x<=R;++x)for(int y=x;y<=R;++y)for(int u=0;u<=k;++u)ans+=(A[x][y][u]-(u?A[x][y][u-1]:0))*(B[x][y][k-u]-(k-u?B[x][y][k-u-1]:0));
        solve(l,mid,L,R),solve(mid+1,r,L,R);
    }else{
        const int mid=L+R>>1;
        for(int i=l;i<=r;++i)for(int j=i;j<=r;++j)memset(A[i][j],0,sizeof**A),memset(B[i][j],0,sizeof**B);
        for(int K=0;K<=k;++K){
            for(int x=l;x<=r;++x){
                int up=L,down=R;
                for(int y=x;y<=r;++y){
                    while(up<=mid&&sum(x,y,up,mid)>K)++up;
                    while(down>mid&&sum(x,y,mid+1,down)>K)--down;
                    A[x][y][K]=mid-up+1,B[x][y][K]=down-mid;
                }
            }
        }
        for(int x=l;x<=r;++x)for(int y=x;y<=r;++y)for(int u=0;u<=k;++u)ans+=(A[x][y][u]-(u?A[x][y][u-1]:0))*(B[x][y][k-u]-(k-u?B[x][y][k-u-1]:0));
        solve(l,r,L,mid),solve(l,r,mid+1,R);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)cin>>b[i]+1;
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
    s[i][j]=(b[i][j]^'0')+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    solve(1,n,1,m);
    cout<<ans<<'\n';
    return 0;
}