CF333D 另一种做法

前言

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;
}