【CodeForces】713 D. Animals and Puzzle 动态规划+二维ST表

【题目】D. Animals and Puzzle

【题意】给定n*m的01矩阵，Q次询问某个子矩阵内的最大正方形全1子矩阵边长。n,m<=1000，Q<=10^6。

【算法】动态规划DP+二维ST表

【题解】设f[i][j]为以(i,j)为右下角的最大正方形全1子矩阵。

f[i][j]=min{ f[i-1][j-1] , f[i][j-1] , f[i-1][j] }+1

然后用二维ST表处理f[i][j]的子矩阵最小值。

对于每次询问，二分边长x，答案即子矩阵(x1+x-1,y1+x-1)~(x2,y2)的f最小值。

特别注意：若是ST表直接处理二维，需要先预处理[0][1]和[1][0]的情况（即只有一条边的情况）。比较推荐先处理每行后再处理列。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
const int maxn=1002;
int a[maxn][maxn],c[maxn][maxn][11][11],logs[maxn],n,m;
void ST(){
    logs[0]=-1;for(int i=1;i<=max(n,m);i++)logs[i]=logs[i>>1]+1;
    for(int k=0;(1<<k)<=n;k++)for(int l=0;(1<<l)<=m;l++)if(k||l)
    for(int i=1;i+(1<<k)-1<=n;i++)for(int j=1;j+(1<<l)-1<=m;j++){
        if(!k){c[i][j][k][l]=max(c[i][j][k][l-1],c[i][j+(1<<(l-1))][k][l-1]);continue;}
        if(!l){c[i][j][k][l]=max(c[i][j][k-1][l],c[i+(1<<(k-1))][j][k-1][l]);continue;}
        int s=max(c[i][j][k-1][l],c[i][j][k][l-1]);
        c[i][j][k][l]=max(c[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1],s);
    }
}
int query(int x1,int y1,int x2,int y2){
    if(x2<x1||y2<y1)return -1;
    int k=logs[x2-x1+1],l=logs[y2-y1+1];
    int s=max(c[x1][y1][k][l],c[x2-(1<<k)+1][y2-(1<<l)+1][k][l]);
    int t=max(c[x2-(1<<k)+1][y1][k][l],c[x1][y2-(1<<l)+1][k][l]);
    return max(s,t);
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        a[i][j]=read();
        if(a[i][j])c[i][j][0][0]=min(c[i-1][j-1][0][0],min(c[i-1][j][0][0],c[i][j-1][0][0]))+1;
    }
    ST();
    int T=read();
    while(T--){
        int x1=read(),y1=read(),x2=read(),y2=read();
        int l=0,r=min(x2-x1+1,y2-y1+1)+1,mid;
        while(l<r){
            mid=(l+r)>>1;
            if(query(x1+mid-1,y1+mid-1,x2,y2)>=mid)l=mid+1;else r=mid;
        }
        printf("%d\n",l-1);
    }
    return 0;
}