[CF 371 D] Animals and Puzzle

1. DP[i][j] = (i, j)가 오른쪽 밑 모서리인 정사각형의 최대 크기

1-(1). (i,j) 가 0인 경우 -> DP[i][j]=0;

1-(2). (i,j) 가 1인 경우 -> min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1

2. parametric search

3. 쿼리의 정답이 특정 값 mid 이상인지 여부는 DP 배열을 소스로 만든 sparse table을 통해 바로 알 수 있음.

// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef short node_type;
 
namespace MIN_ver{
    node_type INIT = 1000000000;
    node_type node_calc(node_type n1, node_type n2){return min(n1,n2);}
}
 
namespace MAX_ver{
    node_type INIT = 0;
    node_type node_calc(node_type n1, node_type n2){return max(n1,n2);}
}
 
using namespace MAX_ver;
 
const int N = 1005, log_N = 11, M = 1005, log_M = 11;
 
struct sparse_table{ // 0-based
    int n1,m1;
    node_type T[N][M][log_N][log_M];
    node_type res[N][M]; // res : 기존 배열
    int cal_d[N+M];
    void init(int n2,int m2){
        n1=n2,m1=m2;
        for(int i=1; i<N+M; i++){
            cal_d[i] = cal_d[i-1];
            while((1<<cal_d[i])<=i) cal_d[i]++;
            cal_d[i]--;
        }
        for(int i=0; i<n1; i++)
            for(int j=0; j<m1; j++)
                T[i][j][0][0] = res[i][j];
        for(int di=0; di<log_N; di++){
            if(di==0){
                for(int dj=1; dj<log_M; dj++)
                    for(int i=0; i<n1; i++)
                        for(int j=0; j+(1<<dj)<=m1; j++)
                            T[i][j][di][dj] = node_calc(T[i][j][di][dj-1], T[i][j+(1<<(dj-1))][di][dj-1]);
            }
            else{
                for(int dj=0; dj<log_M; dj++)
                    for(int i=0; i+(1<<di)<=n1; i++)
                        for(int j=0; j+(1<<dj)<=m1; j++)
                            T[i][j][di][dj] = node_calc(T[i][j][di-1][dj], T[i+(1<<di-1)][j][di-1][dj]);
            }
        }
    }
    node_type query(int x1, int y1,int x2, int y2){
        if(x1>x2 || y1>y2) return INIT;
        int d1 = cal_d[x2-x1+1];
        int d2 = cal_d[y2-y1+1];
        int x3 = x2-(1<<d1)+1;
        int y3 = y2-(1<<d2)+1;
        node_type ret = T[x1][y1][d1][d2];
        ret = node_calc(ret, T[x1][y3][d1][d2]);
        ret = node_calc(ret, T[x3][y1][d1][d2]);
        ret = node_calc(ret, T[x3][y3][d1][d2]);
        return ret;
    }
}table;
 
int n,m;
int a[N][N];
int sum[N][N];
 
bool chk(int x1,int y1,int x2,int y2){
    return (x2-x1+1)*(y2-y1+1) == sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
 
int main(){
    scanf("%d %d",&n,&m);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d",&a[i][j]);
            sum[i][j] = a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            table.res[i][j] = 0;
            for(int k=i-table.res[i-1][j-1]; k<=i; k++){
                if(chk(k,j-(i-k),i,j)){
                    table.res[i][j] = i-k+1;
                    break;
                }
            }
        }
    }
    table.init(n+1,m+1);
    int t;
    scanf("%d",&t);
    while(t--){
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        int l = 0;
        int r = min(x2-x1+1, y2-y1+1)+1;
        while(l+1<r){
            int mid = (l+r)/2;
            if(table.query(x1+mid-1,y1+mid-1,x2,y2)<mid) r = mid;
            else l = mid;
        }
        printf("%d\n",l);
    }
    return 0;
}