题目描述

输入

输出

样例输入

3 4

1 1 0 1

0 1 1 0

0 1 1 0

5

1 1 2 3

2 1 3 2

3 2 3 4

1 1 3 4

1 2 3 4

样例输出

1

1

1

2

2

数据范围

解法

设f[i][j]为以(i,j)为右下角的正方形的最大边长。

则f[i][j]=min(f[i−1][j],f[i−1][j−1],f[i][j−1])+1(a[i][j]=1)

考虑利用f来求答案。

对于询问(x1,y1,x2,y2)：

显然ans=min(f[x][y],x−x1+1,y−y1+1)

二分答案mid，如果矩阵(x1+mid-1,y1+mid-1,x2,y2)的f最大值大于或等于mid，那么mid合法。

静态子矩阵求最大值，考虑使用二维RMQ。

总的时间复杂度为O(T∗log(n2))。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) int(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="square.in";

const char* fout="square.out";

const int inf=0x7fffffff;

const int maxn=1007,maxk=10;

int n,m,t,i,j,k,l,lef,mid,rig;

int f[maxn][maxn],g[maxk][maxk][maxn][maxn];

int getmax(int sx,int sy,int tx,int ty){

    int i=0,j=0;

    while (sx+(1<<(i+1))-1<=tx) i++;

    while (sy+(1<<(j+1))-1<=ty) j++;

    return max(max(g[i][j][sx][sy],g[i][j][tx-(1<<i)+1][sy]),max(g[i][j][sx][ty-(1<<j)+1],g[i][j][tx-(1<<i)+1][ty-(1<<j)+1]));

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%d%d",&n,&m);

    for (i=1;i<=n;i++){

        for (j=1;j<=m;j++){

            scanf("%d",&k);

            if (k) f[i][j]=min(f[i][j-1],min(f[i-1][j-1],f[i-1][j]))+1;

            else f[i][j]=0;

            g[0][0][i][j]=f[i][j];

        }

    }

    for (i=0;(1<<i)<=n;i++){

        for (j=0;(1<<j)<=m;j++){

            if (i==0 && j==0) continue;

            for (k=1;k+(1<<i)-1<=n;k++)

                for (l=1;l+(1<<j)-1<=m;l++){

                    if (j==0) g[i][j][k][l]=max(g[i-1][j][k][l],g[i-1][j][k+(1<<(i-1))][l]);

                    else g[i][j][k][l]=max(g[i][j-1][k][l],g[i][j-1][k][l+(1<<(j-1))]);

                }

        }

    }

    scanf("%d",&t);

    for (;t;t--){

        scanf("%d%d%d%d",&i,&j,&k,&l);

        if (getmax(i,j,k,l)==0) printf("0\n");

        else {

            lef=1;

            rig=min(k-i+1,l-j+1);

            int l1=lef,r1=rig;

            while (lef<rig){

                mid=(lef+rig)/2;

                if (getmax(i+mid-1,j+mid-1,k,l)>=mid) lef=mid;

                else rig=mid-1;

                if (l1==lef && r1==rig) break;

                else l1=lef,r1=rig;

            }

            if (getmax(i+rig-1,j+rig-1,k,l)>=rig) lef=rig;

            printf("%d\n",lef);

        }

    }

    return 0;

}

启发

静态子矩阵求和可以使用RMQ。

这类型（无修改离线多次询问）的问题可以这样考虑：

1.由询问次数决定时间复杂度；

2.考虑一次询问如何在规定复杂度内求出答案。

3.考虑预处理在2中所需要的信息。

这题类似于妮厨的愤怒，那样处理三元取最值。