【NOIP2016提高A組五校聯考4】square

題目

分析

首先，設 fi,j 表示最大的以(i,j)為左下角的正方形的邊長。

轉移顯然， fi,j=max(fi−1,j,fi,j−1,fi−1,j−1)+1

接着，再設 gi,j,k,l 表示在以 (k,l) 為左上角， (k+2i−1,l+2j−1) 為右下角的矩陣中，最大的f。

二維rmq就不講了。

假設詢問矩陣(x,y,x1,y1)，

二分答案ans（想想為什麼？）

用rmq看紅色區域中的最大f值是否合法。

注意：出題人将輸入調的太大了，要打讀入優化。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
const int maxlongint=;
const int mo=;
const int N=;
using namespace std;
int f[N][N],n,m,T,g[][][N][N],a[N][N],logn,logm;
int read(int &n)
{
    char ch=' ';
    int q=,w=;
    for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
    if(ch=='-') w=-,ch=getchar();
    for(;ch>='0' && ch<='9';ch=getchar()) q=q*+ch-;n=q*w;
    return n;
}
int min2(int x,int y)
{
    if(x>y) x=y;
    return x;
}
int max2(int x,int y)
{
    if(x<y) x=y;
    return x;
}
int min1(int x,int y,int z)
{
    if(x>y) x=y;
    if(x>z) x=z;
    return x;
}
int max1(int x,int y,int z,int a)
{
    if(x<y) x=y;
    if(x<z) x=z;
    if(x<a) x=a;
    return x;
}
int pref()
{
    int i,j;
    for(i=;i<=n;i++)
        for(j=;j<=m;j++)
            if(a[i][j])
                g[][][i][j]=f[i][j]=min1(f[i-][j-],f[i-][j],f[i][j-])+;  
}
int prermq()
{
    int i,j,k,l;
    for(i=;i<=logn;i++)
    {

        for(j=;j<=logm;j++)
        {
            if(j+i!=)
            {
                int p=<<(i-);
                int q=<<(j-);
                for(k=;k<=n;k++)
                    if(k+p<=n)
                    {
                        for(l=;l<=m;l++)
                            if(l+q<=m)
                            {
                                if(i!= && j!=)
                                    g[i][j][k][l]=max1(g[i-][j-][k][l],g[i-][j-][k+p][l],g[i-][j-][k+p][l+q],g[i-][j-][k][l+q]);
                                else
                                if(i==)
                                    g[i][j][k][l]=max2(g[i][j-][k][l],g[i][j-][k][l+q]);
                                else
                                if(j==)
                                    g[i][j][k][l]=max2(g[i-][j][k][l],g[i-][j][k+p][l]);
                            }
                            else break;
                    }
                    else break;
            }
        }
    }
}
int rmq(int x,int y,int x1,int y1)
{
    int p=log2(x1-x+),q=log2(y1-y+);
    return max1(g[p][q][x][y],g[p][q][x1-(<<p)+][y],g[p][q][x][y1-(<<q)+],g[p][q][x1-(<<p)+][y1-(<<q)+]);
}
int rf(int x,int y,int x1,int y1)
{
    int lx=x1-x+,ly=y1-y+,l=,r=min2(lx,ly);
    while(l<r-)
    {
        int mid=(l+r)/;
        if(rmq(x+mid-,y+mid-,x1,y1)>=mid)
            l=mid;
        else
            r=mid-;
    }
    if(rmq(x+r-,y+r-,x1,y1)>=r)
        printf("%d\n",r);
    else
    if(rmq(x+l-,y+l-,x1,y1)>=l)
        printf("%d\n",l);
    else
        printf("0\n");
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
        {
            read(a[i][j]);
            f[i][j]=a[i][j];
        }
    pref();
    logn=log2(n);
    logm=log2(m);
    prermq();
    scanf("%d",&T);
    int x1,x2,y1,y2;
    for(int i=;i<=T;i++)
    {
        read(x1);
        read(y1);
        read(x2);
        read(y2);
        rf(x1,y1,x2,y2);
    }
}