Description：

给定 $k,n$ ，和 $n\times n$ 的矩阵，求一个子矩形满足权值和在 $[k,2k]$ 之间。

$1\leqslant n\leqslant 2000$

Solution：

如果存在一个元素 $x\in[k,2k]$ ，那么直接把这个点取出来就行了。

如果存在一个元素 $x>2k$ ，那么最后选出的子矩阵一定不包含他，把这些点称为坏点，然后用单调栈或者悬线法求出最大权值子矩阵，如果权值和 $<k$ ，那就无解，如果合法，直接退出，否则权值和一定 $>2k$ ，考虑怎么构造一个子矩阵出来，假设子矩阵行数不为 $1$ ，列同理，那么拿出边界上的一行，如果这一行或者剩下的权值和 $\in[k,2k]$ ，那就找到了，如果都 $>2k$ ，那就去掉一个，剩下的继续做，如果有一个 $<k$ ，那就把那个删掉，剩下的还是可以继续做，不断重复这个过程最后一定可以找到解。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int k,n;

#define MAXN 2010

int v[MAXN][MAXN];

bool bad[MAXN][MAXN];

int up[MAXN][MAXN];

int s[MAXN][MAXN];

int stack[MAXN],top = 0;

int lef[MAXN][MAXN],rig[MAXN][MAXN];

int sum(int i1,int j1,int i2,int j2)

{

	return s[i2][j2] - s[i1 - 1][j2] - s[i2][j1 - 1] + s[i1 - 1][j1 - 1];

}

int main()

{

	scanf("%d%d",&k,&n);

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

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

			scanf("%d",&v[i][j]);

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

	{

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

		{

			if(k <= v[i][j] && v[i][j] <= 2 * k)

			{

				cout << j << " " << i << " " << j << " " << i << endl;

				return 0;

			}

		}

	}

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

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

			if(v[i][j] > 2 * k)

				bad[i][j] = true;

	memset(up,-1,sizeof(up));

	memset(up[0],0,sizeof(up[0]));

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

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

			up[i][j] = (bad[i][j] ? 0 : up[i - 1][j] + 1);

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

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

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

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

	{

		top = 0;stack[++top] = 0;

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

		{

			while(top > 0 && up[i][stack[top]] >= up[i][j])--top;

			lef[i][j] = stack[top] + 1;

			stack[++top] = j;

		}

		top = 0;stack[++top] = n + 1;

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

		{

			while(top > 0 && up[i][stack[top]] >= up[i][j])--top;

			rig[i][j] = stack[top] - 1;

			stack[++top] = j;

		}

	}

	int ax,ay,bx,by,ans = 0;

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

	{

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

		{

			if(bad[i][j])continue;

			if(sum(i - up[i][j] + 1,lef[i][j],i,rig[i][j]) > ans)

			{

				ax = i - up[i][j] + 1;ay = lef[i][j];

				bx = i;by = rig[i][j];

				ans = sum(i - up[i][j] + 1,lef[i][j],i,rig[i][j]);

			}

		}

	}

	if(sum(ax,ay,bx,by) < k)

	{

		puts("NIE");

		return 0;

	}

	if(sum(ax,ay,bx,by) <= 2 * k)

	{

		cout << ay << " " << ax << " " << by << " " << bx << endl;

		return 0;

	}

	while(sum(ax,ay,bx,by) > 2 * k)

	{

		if(ax != bx)

		{

			int us = sum(ax,ay,ax,by);

			int ds = sum(ax + 1,ay,bx,by);

			if(k <= us && us <= 2 * k)

			{

				cout << ay << " " << ax << " " << by << " " << ax << endl;

				return 0;

			}

			if(k <= ds && ds <= 2 * k)

			{

				cout << ay << " " << ax + 1 << " " << by << " " << bx << endl;

				return 0;

			}

			if(us < k)

			{

				++ax;

			}

			else

			{

				bx = ax;

			}

		}

		else

		{

			++ay;

			if(k <= sum(ax,ay,bx,by) && sum(ax,ay,bx,by) <= 2 * k)

			{

				cout << ay << " " << ax << " " << by << " " << bx << endl;

			}

		}

	}

	return 0;

}