<span>codeforces713D Animals and Puzzle（二维倍增）</span>
引自：http://www.cnblogs.com/qscqesze/p/5929117.html
题意：
给你一个01矩阵，然后Q次询问，每次询问一个矩形区域中，最大的全一正方形的边长是多少。
思路：
首先考虑Dp，dp[i][j]表示以(i,j)位置为右下角，最大的正方形边长是多少，显然dp[i][j]=min(dp[i-1][j],dp[j][i-1],dp[i-1][j-1])+1
然后我们做出这个dp之后，我们怎么做呢？
直接二分答案，假设我们二分的答案为mid，显然在这个矩形区域的左上角的点是废点，然后查询剩下的点的最大值，是否大于等于m就行了。
这个可以用二维线段树，也可以用二维倍增去做就好了。
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x) { char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int N=1e3+10; const int M=10; int f[M][M][N][N],lg[N],n,m,q,x,x1,x2,y1,y2; void build() { rep(i,2,N) lg[i]=lg[i/2]+1; for(int i=1;i<=n;i++) for(int k2=1;(1<<k2)<=m;k2++) for(int j=1;j<=m-(1<<k2)+1;j++) f[0][k2][i][j]=max(f[0][k2-1][i][j],f[0][k2-1][i][j+(1<<(k2-1))]); for(int k1=1;(1<<k1)<=n;k1++) for(int i=1;i<=n-(1<<k1)+1;i++) for(int k2=0;(1<<k2)<=m;k2++) for(int j=1;j<=m-(1<<k2)+1;j++) f[k1][k2][i][j]=max(f[k1-1][k2][i][j],f[k1-1][k2][i+(1<<(k1-1))][j]); } int query(int x1,int y1,int x2,int y2) { int k1=lg[x2-x1+1],k2=lg[y2-y1+1]; x2=x2-(1<<k1)+1; y2=y2-(1<<k2)+1; return max(max(f[k1][k2][x1][y1],f[k1][k2][x1][y2]),max(f[k1][k2][x2][y1],f[k1][k2][x2][y2])); } int main() { #ifndef ONLINE_JUDGE //IN #endif rd(n),rd(m); rep(i,1,n)rep(j,1,m) { rd(x); if(x) f[0][0][i][j]=min(f[0][0][i-1][j],min(f[0][0][i-1][j-1],f[0][0][i][j-1]))+1; } build(); rd(q); while(q--) { rd(x1),rd(y1),rd(x2),rd(y2); int l=0,r=min(x2-x1,y2-y1)+1,ans=0; while(l<=r) { int mid=l+r>>1; if(query(x1+mid-1,y1+mid-1,x2,y2)>=mid) l=mid+1,ans=mid; else r=mid-1; } ou(ans); } return 0; }
