bzoj 1127 KUP —— 最大子矩形+答案构造

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1127

首先，把权值 > 2*k 的点作为“坏点”，然后在图中用悬线法找权值最大的子矩形；

如果权值最大的子矩形的权值 < k ，那么无解；

否则，针对这个子矩形，一列一列地删掉元素，某一时刻权值一定会变成 k~2*k 或 < k；

如果变成 k~2*k ，直接输出即可；

如果变成 < k，那么刚才删掉的那一列的权值 > k；

针对那一列，如果权值和就是 k~2*k，输出那一列；

否则，针对这一列，一个一个删除元素，因为此时元素的权值都是 < k 的，所以总会有某一时刻删成 k~2*k，即为答案；

注意输出的坐标是 列-行 !!!

还要注意一个一个删除列上的元素时，符合答案后的坐标是 i+1 !!!

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=;

int n,k,v[xn][xn],l[xn][xn],r[xn][xn],s[xn][xn];

ll sum[xn][xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

ll get(int a,int b,int c,int d){return sum[c][d]-sum[a-][d]-sum[c][b-]+sum[a-][b-];}

int main()

{

  k=rd(); n=rd(); int a=,b=,c,d;

  for(int i=;i<=n;i++)

    {

      int tmp=;

      for(int j=;j<=n;j++)

        {

          v[i][j]=rd();

          sum[i][j]=sum[i][j-]+sum[i-][j]-sum[i-][j-]+v[i][j];

          if(v[i][j]>=k&&v[i][j]<=*k)a=i,b=j;

          if(v[i][j]>*k){tmp=j+; continue;}

          s[i][j]=s[i-][j]+;

          if(v[i-][j]>*k||i==)l[i][j]=tmp;

          else l[i][j]=max(tmp,l[i-][j]);

        }

      tmp=n;

      for(int j=n;j;j--)

        {

          if(v[i][j]>*k){tmp=j-; continue;}

          if(v[i-][j]>*k||i==)r[i][j]=tmp;

          else r[i][j]=min(tmp,r[i-][j]);

        }

    }

  if(a){printf("%d %d %d %d\n",b,a,b,a); return ;}

  ll mxs=;

  for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

      {

        if(v[i][j]>*k)continue;

        int ta=i-s[i][j]+,tb=l[i][j],tc=i,td=r[i][j];

        ll ts=get(ta,tb,tc,td);

        if(ts<k)continue;

        if(ts>mxs)mxs=ts,a=ta,b=tb,c=tc,d=td;

      }

  if(!mxs){printf("NIE\n"); return ;}

  if(mxs>=k&&mxs<=*k){printf("%d %d %d %d\n",b,a,d,c); return ;}

  for(int j=b;j<=d;j++)

    {

      mxs-=get(a,j,c,j);

      if(mxs>=k&&mxs<=*k){printf("%d %d %d %d\n",j+,a,d,c); return ;}

      else if(mxs<k)

        {

          ll ts=get(a,j,c,j);

          if(ts>=k&&ts<=*k){printf("%d %d %d %d\n",j,a,j,c); return ;}

          for(int i=a;i<=c;i++)

            {

              ts-=v[i][j];

              if(ts>=k&&ts<=*k){printf("%d %d %d %d\n",j,i+,j,c); return ;}//i+1!!!

            }

        }

    }

  return ;

}