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