前言
duel 的时候做的题，做出来的时候感觉很神，看了题解做法感觉自己是个傻逼。
本做法时间复杂度是 \(O(n^{\tfrac{5}{2}})\)，可以作为补充了解。
题解
一个矩阵四个角的最大值有点烦，我们把它们排序，从小到大依次插入，则问题变为：
在 \(n\times m\) 的平面中，每次插入一个点，求在什么时候会出现一个矩形的四个顶点。
我们发现插入点数并不多，自然想到直接每次暴力向左右扫描。
设插入点数为 \(k\)，则时间复杂度为 \(O(mk)\)。
那么插入点数的上界是多少呢？
其实我也不会证qaq
感谢EI老师 @Elegia 给出一篇博客，证明了插入点数的上界是 \(O(n\sqrt{n})\)，有兴趣的可以在此处阅读。
Code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
struct point{
LL x,y,val;
}b[1000005];
LL n,i,j,k,m,cnt=0;
LL a[1005][1005];
bool flag[1005][1005];
bool tmp[1005][1005];
LL cmp(point x,point y){
return x.val>y.val;
}
int main(){
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%lld",&a[i][j]);
b[++cnt].val=a[i][j];
b[cnt].x=i;b[cnt].y=j;
}
}
sort(b+1,b+cnt+1,cmp);
for(i=1;i<=cnt;i++){
flag[b[i].x][b[i].y]=true;
for(j=1;j<b[i].x;j++)
if(flag[j][b[i].y]==true){
if(tmp[j][b[i].x]==true){
printf("%lld",b[i].val);
return 0;
}
else{
tmp[j][b[i].x]=true;
}
}
for(j=b[i].x+1;j<=n;j++)
if(flag[j][b[i].y]==true){
if(tmp[b[i].x][j]==true){
printf("%lld",b[i].val);
return 0;
}
else{
tmp[b[i].x][j]=true;
}
}
}
return 0;
}