CF1731D 题解
题面
原题传送门（洛谷）
原题传送门（codeforces）
思路
注意到 \(n\times m\leqslant10^6\)，所以本题允许 \(nm\log\min(n,m)\) 的做法。
于是考虑二分答案，每个点的值就是 \([a_{i,j}\geqslant l]\)，于是统计二维前缀和，暴力地遍历每一个正方形，只要有一个正方形的和等于正方形内数的个数，则就存在满足题意的此变长的正方形。
于是就做完了。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define ll long long
using namespace std;
ll n,m;
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
ll gs(ll x, ll y, ll xx, ll yy, vector<vector<ll> >& s){return s[xx][yy]-s[x-1][yy]-s[xx][y-1]+s[x-1][y-1];}
bool check(ll l, vector<vector<ll> >& a){vector<vector<ll> > s(n+5,vector<ll>(m+5,0));for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]>=l?1:0);for(int i=l; i<=n; i++) for(int j=l; j<=m; j++){ll x=i-l+1,y=j-l+1;if(gs(x,y,i,j,s)==l*l) return true;}return false;
}
void solve(){n=read();m=read();vector<vector<ll> > a(n+5,vector<ll>(m+5));for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) a[i][j]=read();ll l=1,r=min(n,m)+1;while(l<r){ll mid=l+r>>1;if(check(mid,a)) l=mid+1;else r=mid;}write(l-1);putchar('\n');
}
int main(){ll T=read();while(T--)solve();return 0;
}