NOIP提高組【JZOJ4817】square

Description

Data Constraint

Solution

我們首先可以預處理出f[i][j]表示以（i，j）為右下角的最大正方形的邊長。這顯然可以在輸入時處理出來。 f[i][j]=min(f[i−1][j−1],f[i−1][j],f[i][j−1])+1 。對于一個詢問（x,y,xx,yy），我們其實是可以二分答案的。假設我們目前二分出來的答案為mid，那麼我們就可以在（x+mid-1,y+mid-1,xx,yy）這個區間那裡找一個最大正方形，若最大正方形的邊長大于mid就往右走。那麼現在問題是：如何在（x+mid-1,y+mid-1,xx,yy）這個區間内找一個最大的f[i][j]呢？我們想到用二維rmq來解決。設g[x][y][i][j]表示（i- 2x+1 ，j- 2y+1 ,i,j）這個區間内的最大的f值。然後設t= log2xx−(x+mid−1) ，k= log2yy−(y+mid−1) ，那麼一個詢問（x+mid-1,y+mid-1,xx,yy）的中的最大f值則是 max(g[t][k][xx][yy],g[t][k][x+mid−1+2t][y+mid−1+2k],g[t][k][x+mid−1+2t][yy],g[t][k][xx][y+mid−1+2k]) 。（若看不懂的話可以手動畫一下圖，畫一下就懂了。）注意一下，log的運算在c++中是很慢的，建議手打，否則你會像部落客一樣卡了3小時的常還是90分……

代碼

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=;
int a[maxn][maxn],n,i,t,j,k,l,m,p,x,y,xx,yy,r,mid,l1;
int f[maxn][maxn],g[][][maxn][maxn],ans;
int pan(int x,int y){
    int i,j,t=,k=;
    while (x+(<<(t+))-<=xx) t++;
    while (y+(<<(k+))-<=yy) k++;
    ans=g[t][k][xx][yy];
    if (g[t][k][x+(<<t)-][y+(<<k)-]>ans) ans=g[t][k][x+(<<t)-][y+(<<k)-];
    if (ans<g[t][k][x+(<<t)-][yy]) ans=g[t][k][x+(<<t)-][yy];
    if (ans<g[t][k][xx][y+(<<k)-]) ans=g[t][k][xx][y+(<<k)-];
    return ans;
}
int get(){
    char ch=getchar();int x=;
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*+ch-'0',ch=getchar();
    return x;
}
int main(){
    freopen("square.in","r",stdin);freopen("square.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=;i<=n;i++)
        for (j=;j<=m;j++){
            scanf("%d",&a[i][j]);
            if (a[i][j]) f[i][j]=min(min(f[i-][j-],f[i-][j]),f[i][j-])+;
            g[][][i][j]=f[i][j];
        }
    l1=log(n)/log();
    p=log(m)/log();
    for (i=;i<=l1;i++)
        for (j=;j<=p;j++){
            if (!i && !j) continue;
            for (x=(<<i);x<=n;x++)
                for (y=(<<j);y<=m;y++){
                    if (i){
                        if (g[i-][j][x][y]>g[i-][j][x-(<<(i-))][y]) g[i][j][x][y]=g[i-][j][x][y];
                        else g[i][j][x][y]=g[i-][j][x-(<<(i-))][y];
                    }
                    else{
                        if (g[i][j-][x][y]>g[i][j-][x][y-(<<(j-))]) g[i][j][x][y]=g[i][j-][x][y];
                        else g[i][j][x][y]=g[i][j-][x][y-(<<(j-))];
                    }
                }
        }
    scanf("%d",&m);
    while (m){
        scanf("%d%d%d%d",&x,&y,&xx,&yy);
        //x=get();y=get();xx=get();yy=get();
        l=;r=min(yy-y+,xx-x+);
        while (l<r){
            mid=(l+r+)/;
            if (pan(x+mid-,y+mid-)>=mid) l=mid;
            else r=mid-;
        }
        printf("%d\n",l);
        m--;
    }
}