[暑假集训Day4T2]卡拉赞之夜

抹茶学长给的标程可以被卡到O(N²M²)???

考虑二分答案+暴力check+离散化+卡常数

首先进行离散化，其实判重的话会更快，但是由于矩阵元素大小太大了，hash判重MLE，所以我就直接记录了NM个元素之后排序，即可二分离散化后数组中的下标。

二分离散化数组的下标，对于每一个下标考虑暴力check。设数组pd，当pd[i][j]=1时，表示F(i,j)>=mid，对于需验证的答案mid，首先令mid--，这样只需判断比mid大的数即可（常数优化）。之后用O(NM)的时间计算pd数组（可以用bitset进行常常数优化，蒟蒻这里不太会，直接开的bool数组）这里有一个很重要的优化，如果一行中1的数量小于2，它一定不能作为矩阵的上界和下界，O(N)记录即可。最后枚举矩阵上下界，设上界为i行，下界为j行，枚举k列。当pd[i][k]==pd[j][k]==1时，可以作为矩阵的两个角，如果两列中列有两组以上这样的情况，那么答案mid是可行的，传回成功信息，如果对于所有行都不行的话，那么传回失败信息。最后，能用快读快写的地方尽量用快读快写，能用位运算的地方尽量用位运算。

加入以上优化后我成功地把O(N²M(logNM))的算法(N,M≤1000)卡到了568ms(逃)

参考代码如下：

#include<iostream>
#include<bitset>
#include<cstdio>
#include<algorithm>
#include<cstdlib> 
using namespace std;
inline int read() 
{
    int x=0;
    bool f=1;
    char c=getchar();
    for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
    for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    if(f) return x;
    return 0-x;
}
int n,m,f[1010][1010],maxn=-1073741822,minn=1073741822,v[1000001];
inline bool check(int x)
{
    x--;
    bool p[1010]={},pd[1010][1010]={};
    int ct[1010]={};
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(f[i][j]>x)pd[i][j]=1,ct[i]++;
    for(int i=1;i<=n;i++)
    {
        if(ct[i]<2)p[i]=1;
    }
    for(int i=1;i<n;i++)
    {
        if(p[i])continue;
        for(int j=i+1;j<=n;j++)
        {
            if(p[j])continue;
            int cnt=0;
            for(int k=1;k<=m;k++)
                if(pd[i][k]&pd[j][k])
                {
                    cnt++;
                    if(cnt>1) return 1;
                }
        }
    }
    return false;
}
int main()
{
    //srand(20050923);
    int t=0;
    n=read();m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=read();
            v[++t]=f[i][j];
            maxn=max(maxn,f[i][j]);
            minn=min(minn,f[i][j]);
        }
    sort(v+1,v+t+1);
    int l=1,r=t,mid,tot=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(v[mid])) l=mid+1;
        else r=mid-1;
    }
    cout<<v[l-1];
    return 0;
}