$n<=1000,m<=1000$，$n*m$的01矩阵，给$t<=1000000$个询问，每次问一个矩形中最大的1正方形的边长。
先想想不考虑“一个矩形中”的限制，那记$f(i,j)$--以$(i,j)$为右下角的最大的正方形，那
很好，那现在加入一个边界限制，由于边长r的正方形同时也是边长r-1，r-2……的，那来二分答案吧，现在对二分的答案$x$就检查一个区域里的$f$数组中最大的那一个是否大于等于$x$。查静态区间最大，用ST表啦！拓展到二维情况即可。
1 #include<string.h> 2 #include<stdlib.h> 3 #include<stdio.h> 4 //#include<math.h> 5 //#include<assert.h> 6 #include<algorithm> 7 //#include<iostream> 8 //#include<bitset> 9 using namespace std; 10 11 int n,m,t; 12 #define maxn 1011 13 int a[maxn][maxn],Log[maxn];short rmq[maxn][maxn][12][12]; 14 15 int x1,x2,y1,y2; 16 int rmqquery(int x1,int y1,int x2,int y2) 17 { 18 int p=Log[x2-x1+1],q=Log[y2-y1+1]; 19 return max(max(rmq[x1][y1][p][q],rmq[x2-(1<<p)+1][y1][p][q]) 20 ,max(rmq[x1][y2-(1<<q)+1][p][q],rmq[x2-(1<<p)+1][y2-(1<<q)+1][p][q])); 21 } 22 bool check(int len) {return rmqquery(x1+len-1,y1+len-1,x2,y2)>=len;} 23 int main() 24 { 25 scanf("%d%d",&n,&m); 26 for (int i=1;i<=n;i++) 27 for (int j=1;j<=m;j++) 28 scanf("%d",&a[i][j]); 29 for (int i=1;i<=n;i++) 30 for (int j=1;j<=m;j++) 31 if (a[i][j]==0) rmq[i][j][0][0]=0; 32 else rmq[i][j][0][0]=min(rmq[i][j-1][0][0],min(rmq[i-1][j][0][0],rmq[i-1][j-1][0][0]))+1; 33 Log[0]=-1; for (int i=1,to=max(n,m);i<=to;i++) Log[i]=Log[i>>1]+1; 34 for (int q=1;(1<<q)<=m;q++) 35 for (int i=1;i<=n;i++) 36 for (int j=1,to=m-(1<<q)+1;j<=to;j++) 37 rmq[i][j][0][q]=max(rmq[i][j][0][q-1],rmq[i][j+(1<<(q-1))][0][q-1]); 38 for (int p=1;(1<<p)<=n;p++) 39 { 40 for (int i=1,to=n-(1<<p)+1;i<=to;i++) 41 for (int j=1;j<=m;j++) 42 rmq[i][j][p][0]=max(rmq[i][j][p-1][0],rmq[i+(1<<(p-1))][j][p-1][0]); 43 for (int q=1;(1<<q)<=m;q++) 44 for (int i=1,to=n-(1<<p)+1;i<=to;i++) 45 for (int j=1,to=m-(1<<q)+1;j<=to;j++) 46 rmq[i][j][p][q]=max(rmq[i][j][p][q-1],rmq[i][j+(1<<(q-1))][p][q-1]); 47 } 48 scanf("%d",&t); 49 while (t--) 50 { 51 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 52 int L=0,R=min(x2-x1+1,y2-y1+1); 53 while (L<R) 54 { 55 const int mid=(L+R+1)>>1; 56 if (check(mid)) L=mid; 57 else R=mid-1; 58 } 59 printf("%d ",L); 60 } 61 return 0; 62 }