题解 P3474 【[POI2008]KUP-Plot purchase】

kczno1 · 2018-01-14 22:11:24 · 题解

首先一个格子如果权值>2*k是不能选的，如果在[k,2*k]是直接找到了答案的。

那么接下来的问题就是只能选<k的。

可以发现，存在一个子矩形权值和>=k是等价于存在答案的。

因为一个权值和>2*k的矩形一定可以找到一个子矩形权值和>=k且<=2*k。

因为变化是连续的，具体说就是考虑一行一行删，有一行>2*k就一格一格删。

那么只要找到权值和最大的子矩形就好了。

它一定是个极大矩形，所以悬线法即可。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'0');
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
const int N=2000+5;
int n,k,a[N][N];
ll s[N][N];
int up[N],st[N],top;

ll S(int li,int lj,int ri,int rj)
{
    return s[ri][rj]-s[li][rj]-s[ri][lj]+s[li][lj];
}

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    k=read();n=read();
    rep(i,1,n)
    rep(j,1,n)a[i][j]=read();
    rep(i,1,n)
    rep(j,1,n)s[i][j]=s[i][j-1]+a[i][j];
    rep(i,1,n)
    rep(j,1,n)s[i][j]=s[i-1][j]+s[i][j];

    rep(i,1,n)
    rep(j,1,n+1)
    {
        if(a[i][j]<=2*k&&j<=n)
        {
            ++up[j];
            if(a[i][j]>=k)
            {
                printf("%d %d %d %d\n",j,i,j,i);
                exit(0);
            }
        }
        else up[j]=0;
        while(top&&up[st[top]]>=up[j])
        {
            int lj=st[top-1],rj=j-1;
            int li=i-up[st[top]];
            if(S(li,lj,i,rj)>=k)
            {
                while(S(li,lj,i,rj)>2*k)
                {
                    if(S(li,lj,li+1,rj)>2*k)
                    {
                        while(S(li,lj,li+1,rj)>2*k)++lj;
                        printf("%d %d %d %d\n",lj+1,li+1,rj,li+1);
                        exit(0);
                    }
                    ++li;
                }
                printf("%d %d %d %d\n",lj+1,li+1,rj,i);
                exit(0);
            }
            --top;
        }
        if(j<=n)st[++top]=j;
    }
    puts("NIE");
}