Codeforces Round #619 (Div. 2) E. Nanosoft

题目链接
题意：给你一个 $n\ast m，n,m\le 500$n∗m，n,m≤500的有矩阵，问你每个子矩形中最大满足条件的正方形面积。
思路：显然答案最大不超过250，那我们枚举答案即可。设当前答案为 $L$L.，用二维数组记录 $s$s可行与否。
我们检查每个左端点的是否可以构成这个边长 $L$L.,如果可以的话，这个左端点的值就是1，然后遍历所有询问看询问的二维区间是否有值是1即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
#define fi first
#define se second
#define pb push_back
int s[5][503][503];
//0 R 1 G 2 Y 3 B
int n,m,q;
char a[555][555];
int get(int x,int A,int b,int c,int d){
  return s[x][c][d]-s[x][c][b-1]-s[x][A-1][d]+s[x][A-1][b-1];
}
int r1[N],c1[N],r2[N],c2[N];
int ans[N];
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>m>>q;
  for(int i=1;i<=n;i++){
    cin>>a[i]+1;
    for(int j=1;j<=m;j++){
      for(int k=0;k<4;k++)s[k][i][j]=s[k][i-1][j]+s[k][i][j-1]-s[k][i-1][j-1];
      if(a[i][j]=='R')s[0][i][j]++;
      else if(a[i][j]=='G')s[1][i][j]++;
      else if(a[i][j]=='Y')s[2][i][j]++;
      else s[3][i][j]++;
    }
  }
  for(int i=1;i<=q;i++)cin>>r1[i]>>c1[i]>>r2[i]>>c2[i];
  for(int i=1;i<=250;i++){
    if(n<2*i||m<2*i)break;
    for(int j=1;j<=n-2*i+1;j++){
      for(int k=1;k<=m-2*i+1;k++){
        s[4][j][k]=0;
      }
    }
    for(int j=i;j<=n-i;j++){
      for(int k=i;k<=m-i;k++){
        if(get(0,j-i+1,k-i+1,j,k)==i*i&&get(1,j-i+1,k+1,j,k+i)==i*i&&
          get(2,j+1,k-i+1,j+i,k)==i*i&&get(3,j+1,k+1,j+i,k+i)==i*i
        )s[4][j-i+1][k-i+1]=1;
      }
    }
    for(int j=1;j<=n-2*i+1;j++){
      for(int k=1;k<=m-2*i+1;k++){
        s[4][j][k]+=s[4][j-1][k]+s[4][j][k-1]-s[4][j-1][k-1];
      }
    }
    for(int j=1;j<=q;j++){
      if(r2[j]-r1[j]+1>=2*i&&c2[j]-c1[j]+1>=2*i&&get(4,r1[j],c1[j],r2[j]-2*i+1,c2[j]-2*i+1))ans[j]=i;
    }
  }
  for(int i=1;i<=q;i++)cout<<4*ans[i]*ans[i]<<'\n';
  return 0;
}