BZOJ 1127 POI2008 KUP 單調隊列

BZOJ 1127 POI2008 KUP 單調隊列

題目大意：給定一個矩形，求一個子矩形滿足權值和在[k,2k]之間

跪漆子超= =

首先考慮1*n的情況

如果存在[k,2k]之間的點，直接輸出

否則如果存在一個區間滿足和>=k且任意元素

這個很顯然 因為區間內所有元素都

那麼我們把這個結論擴展到二維 也是對的

證明：如果存在一個子矩形滿足和>=k且所有元素

如果這個子矩形的和<=2k，那麼滿足條件直接輸出

否則這個子矩形的和一定>2k

下面討論：

如果這個子矩形只有一行，那麼同上面那種情況

否則我們取這個矩陣最上方的一行和最下方的一行

易知一定存在一行的和<=整個矩形的和的一半

那麼我們把這一行砍掉 由於整個矩形的和>2k 因此砍掉後矩形的和一定>k

這樣無限砍下去，總有一時刻矩形的和會<=2k，此時直接輸出即可

將>2k的點判斷為壞點，用懸線法/單調隊列搞出所有的極大子矩形，依次判斷即可

時間復雜度O(n^2)

#include 
#include 
#include 
#include 
#define M 2020
using namespace std;
int n,k,a[M][M];
long long sum[M][M];
long long Get_Sum(int x1,int y1,int x2,int y2)
{
	return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
void Output(int x1,int y1,int x2,int y2)
{
	while( Get_Sum(x1,y1,x2,y2)>k*2 )
	{
		if(x1==x2)
			y2--;
		else
		{
			if( Get_Sum(x1+1,y1,x2,y2)>=k )
				x1++;
			else
				x2--;
		}
	}
	printf("%d %d %d %d\n",y1,x1,y2,x2);
	exit(0);
}
void Monotonous_Stack(int base,int h[])
{
	static int stack[M],top;
	static int l[M],r[M];
	int i;

	for(top=0,i=1;i<=n+1;i++)
	{
		while( top && h[stack[top]]>h[i] )
			r[stack[top--]]=i-1;
		stack[++top]=i;
	}
	for(top=0,i=n;~i;i--)
	{
		while( top && h[stack[top]]>h[i] )
			l[stack[top--]]=i+1;
		stack[++top]=i;
	}
	for(i=1;i<=n;i++)
		if(h[i])
		{
			long long temp=Get_Sum(base-h[i]+1,l[i],base,r[i]);
			if( temp>=k )
				Output(base-h[i]+1,l[i],base,r[i]);
		}
}
int main()
{
	int i,j;
	cin>>k>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			if( a[i][j]>=k && a[i][j]<=k*2 )
			{
				printf("%d %d %d %d\n",j,i,j,i);
				return 0;
			}
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	static int h[M];
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			h[j]=a[i][j]>k*2?0:h[j]+1;
		Monotonous_Stack(i,h);
	}
	puts("NIE");
	return 0;
}