Codeforces Round 371 D Animals and Puzzle

Task:
给你一张01图,以及t个询问,每个询问为(x1,y1,x2,y2),指在以(x1,y1)为左下角,以(x2,y2)为右下角的矩形中,最大的全为1的矩形的大小.

Sample Input
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

Sample Output
1
1
1
2
2

Solution:
这道题目首先我们先 O(n2) 地处理出以每个点为右下角,组成的矩形最大为多大.
然后对于每个询问,我们先去二分一个答案,然后再在(x1+x,y1+x,x2,y2)中搜一个最大值,如果这个最大值大于x,继续搜比x大的,反之,则搜比x小的.
而求这个最大值,我们可以用二维的st表,St_Table[i][j][k][l]表示以(i,j)为左下角,向右 2k ,向上 2l ,这个矩形中的最大值.
而求一个(x1,y1,x2,y2)的矩形的最大值就是

max(StTable[x1][y1][log2x2−x1][log2y2−y1],

StTable[x1][y2−2log2y2−y1][log2x2−x1][log2y2−y1],

StTable[x2−2log2x2−x1][y1][log2x2−x1][log2y2−y1],

StTable[x2−2log2x2−x1][y2−2log2y2−y1][log2x2−x1][log2y2−y1])

这样就能够A了.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1001
#define LOGM 11
using namespace std;
int mp[M][M],dp[M][M];
int St_Table[M][M][LOGM][LOGM];
int Pow[28],Log[M];
int query(int x,int nx,int y,int ny){
    if(ny<y)return 0;
    int lenx=nx-x+1,leny=ny-y+1;
    int Lgy=Log[leny],Lgx=Log[lenx];
    int xMx=max(St_Table[x][y][Lgx][Lgy],St_Table[x][ny-Pow[Lgy]+1][Lgx][Lgy]);
    int yMx=max(St_Table[nx-Pow[Lgx]+1][y][Lgx][Lgy],St_Table[nx-Pow[Lgx]+1][ny-Pow[Lgy]+1][Lgx][Lgy]);
    return max(xMx,yMx);
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&mp[i][j]);
    for(int i=1;i<=n;i++)dp[i][1]=mp[i][1];
    for(int i=1;i<=m;i++)dp[1][i]=mp[1][i];
    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)
            if(mp[i][j])dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
            else dp[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            St_Table[i][j][0][0]=dp[i][j];
    int rs=0;
    Pow[0]=1;
    for(int i=1;i<28;i++)Pow[i]=Pow[i-1]<<1;
    Log[0]=-1;
    for(int i=1;i<M;i++)Log[i]=Log[i>>1]+1;
    for(int l=0;l+1<LOGM;l++)
        for(int k=0;k+1<LOGM;k++)
            for(int i=1;i<=n-Pow[l]+1;i++)
                for(int j=1;j<=m-Pow[k]+1;j++){
                    int Mj=j+Pow[k],Mi=i+Pow[l];;
                    St_Table[i][j][l][k+1]=max(St_Table[i][j][l][k],St_Table[i][Mj][l][k]);
                    St_Table[i][j][l+1][k]=max(St_Table[i][j][l][k],St_Table[Mi][j][l][k]);
                }
    int cas,x1,x2,y1,y2;
    scanf("%d",&cas);
    while(cas--&&scanf("%d %d %d %d",&x1,&y1,&x2,&y2)!=EOF){
        int ans=0;
        int L=0,R=min(x2-x1+1,y2-y1+1);
        while(L<=R){
            int mid=L+R>>1;
            if(query(x1+mid-1,x2,y1+mid-1,y2)>=mid)ans=mid,L=mid+1;
            else R=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}