[JZOJ4817]square

題目大意

一個 n×m 的網格圖，其中有的格子有障礙，有的沒有。

有 T 個詢問，每次詢問一個子矩形(x1,y1)−(x2,y2)。查詢該子矩形内邊長最大的格點正方形邊長為多少。一個正方形不能包括有障礙的格子。

1≤n,m≤103,T≤106

題目分析

預處理每隔格子作為左上角能做的最大正方形邊長。

一個很顯然的想法（和[TJOI&HEOI2016]str/[JZOJ4614]字元串的想法類似）：二分邊長，轉化為判定性問題，查詢一個子矩形的最大值是否大于等于二分值。

這裡 T 達到了106規模，顯然我們需要一個查詢 O(1) 的二維 RMQ 算法。二維的 ST 表可以勝任這一工作。

二維的 ST 表預處理實際上和一維是差不多的。在其中一維指數為 0 時轉化為一維問題，否則直接讓其中任意一個維一分為二即可。

查詢類似一維情況，分成四個子矩形即可。

時間複雜度O(nmlog2nlog2m+Tlog2n)，卡卡常就過了。

代碼實作

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>

using namespace std;

typedef pair<int,int> P;
#define ft first
#define sd second
#define mkp(a,b) make_pair(a,b)

inline int read()
{
    int x=,f=;
    char ch=getchar();
    while (!isdigit(ch)) f=ch=='-'?-:f,ch=getchar();
    while (isdigit(ch)) x=x*+ch-'0',ch=getchar();
    return x*f;
}

int buf[];

inline void write(int x)
{
    if (x<) putchar('-'),x=-x;
    buf[]=;
    while (x) buf[++buf[]]=x%,x/=;
    if (!buf[]) buf[]=,buf[]=;
    while (buf[]) putchar('0'+buf[buf[]--]);
}

const int N=;
const int LGN=;

int down[N][N],Right[N][N],dwl[N][N],rgl[N][N];
int n,m,T,lgn,head,tail;
int f[LGN][LGN][N][N];
bool a[N][N];
int pw[LGN];
int LOG[N];
P que[N];

void add(P x)
{
    while (head<=tail&&que[tail].ft>=x.ft) tail--;
    que[++tail]=x;
}

int getmin(int x)
{
    while (head<=tail&&que[head].sd>x) head++;
    return que[head].ft;
}

void pre()
{
    for (int i=;i<=n;i++)
        for (int j=m;j>=;j--)
            Right[i][j]=a[i][j]?Right[i][j+]+:;
    for (int j=;j<=m;j++)
        for (int i=n;i>=;i--)
            down[i][j]=a[i][j]?down[i+][j]+:;
    for (int i=;i<=n;i++)
    {
        head=,tail=;
        for (int cur=m,j=m;j>=;j--)
        {
            add(mkp(down[i][j],j));
            while (cur>=j&&getmin(cur)<cur-j+) cur--;
            rgl[i][j]=cur;
        }
    }
    for (int j=;j<=m;j++)
    {
        head=,tail=;
        for (int cur=n,i=n;i>=;i--)
        {
            add(mkp(Right[i][j],i));
            while (cur>=i&&getmin(cur)<cur-i+) cur--;
            dwl[i][j]=cur;
        }
    }
    lgn=trunc(log(n)/log());
    pw[]=;
    for (int i=;i<=lgn;i++) pw[i]=pw[i-]<<;
    for (int i=;i<=n;i++) LOG[i]=trunc(log(i)/log());
    for (int i=;i<=n;i++)
        for (int j=;j<=m;j++)
            f[][][i][j]=min(rgl[i][j]-j+,dwl[i][j]-i+);
    for (int k=;k<=lgn;k++)
        for (int l=;l<=lgn;l++)
            if (k||l)
                for (int i=;i+pw[k]-<=n;i++)
                    for (int j=;j+pw[l]-<=m;j++)
                        if (!k) f[k][l][i][j]=max(f[k][l-][i][j],f[k][l-][i][j+pw[l-]]);
                        else if (!l) f[k][l][i][j]=max(f[k-][l][i][j],f[k-][l][i+pw[k-]][j]);
                        else f[k][l][i][j]=max(f[k][l-][i][j],f[k][l-][i][j+pw[l-]]);
}

int query(int x1,int y1,int x2,int y2)
{
    int lg1=LOG[x2-x1+],lg2=LOG[y2-y1+];
    return max(max(f[lg1][lg2][x1][y1],f[lg1][lg2][x2-pw[lg1]+][y2-pw[lg2]+]),max(f[lg1][lg2][x2-pw[lg1]+][y1],f[lg1][lg2][x1][y2-pw[lg2]+]));
}

int solve(int x1,int y1,int x2,int y2)
{
    int l=,r=min(x2-x1+,y2-y1+),mid,ret=;
    while (l<=r)
    {
        mid=l+r>>;
        if (query(x1,y1,x2-mid+,y2-mid+)>=mid) l=(ret=mid)+;
        else r=mid-;
    }
    return ret;
}

int main()
{
    freopen("square.in","r",stdin),freopen("square.out","w",stdout);
    n=read(),m=read();
    for (int i=;i<=n;i++)
        for (int j=;j<=m;j++)
            a[i][j]=read();
    pre();
    for (T=read();T--;)
    {
        int x1=read(),y1=read(),x2=read(),y2=read();
        write(solve(x1,y1,x2,y2)),putchar('\n');
    }
    fclose(stdin),fclose(stdout);
    return ;
}