自动搬运

查看原文

来自洛谷，原作者为

	kczno1 **

搬运于2025-08-24 21:49:21，当前版本为作者最后更新于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");
}