似曾相识的感觉
考虑另一个判断问题，给定一个k，问这个k是否可行
- 存在矩形和\(sum>2k\)，则该矩阵不对判定做出贡献
- 存在矩形和\(sum\in [k,2k]\)，则我们找到了一个解
于是判掉这两种情况，专心讨论\(sum<k\)的矩形
找到\(sum<k\)的极大矩形，按它的和\(S\)讨论
- \(S<k\)，则无解
- \(S\in [k,2k]\)，则我们找到了一个解
- \(S>2k\)，递归成小矩形继续求解
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN = 2005;
int n,m;
signed l[MAXN][MAXN],a[MAXN][MAXN],r[MAXN][MAXN],h[MAXN][MAXN];
int sum[MAXN][MAXN];
int Sum(int x,int y,int u,int v){return sum[u][v]+sum[x-1][y-1]-sum[x-1][v]-sum[u][y-1];}
inline void print(int x,int y,int u,int v){
while(Sum(x,y,u,v)>2*m){
if(x==u)
v--;
else if(Sum(x+1,y,u,v)>=m)
x++;
else
u--;
}
printf("%lld %lld %lld %lld\n",y,x,v,u);exit(0);
}
signed main(){
scanf("%lld%lld",&m,&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%lld",&a[i][j]);
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
if(a[i][j]>=m&&a[i][j]<=m*2){
printf("%lld %lld %lld %lld\n",j,i,j,i);
return 0;
}
a[i][j]=(a[i][j]<=m*2);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!a[i][j])continue;
l[i][j]=r[i][j]=h[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!a[i][j])continue;
if(a[i-1][j])h[i][j]+=h[i-1][j];
if(a[i][j-1])l[i][j]+=l[i][j-1];
}
for(int j=n;j>=1;j--){
if(!a[i][j])continue;
if(a[i][j+1])r[i][j]+=r[i][j+1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!a[i][j])continue;
if(h[i][j]<=1)continue;
l[i][j]=min(l[i-1][j],l[i][j]);
r[i][j]=min(r[i-1][j],r[i][j]);
int x=i-h[i][j]+1,u=i;
int y=j-l[i][j]+1,v=j+r[i][j]-1;
if(Sum(x,y,u,v)>=m)print(x,y,u,v);
}
}
puts("NIE");
}