博客

题意：每个监控都监控到一个矩形区域，问给定的矩形区域能不能完全被监控覆盖。

思路：如果对每个监控内的范围每次都去逐个改变的话会TLE…这时候类似一维前缀和差分的思想，采用二维差分，思想和一维类似，只是把图拓展到二维，由于监控重不重复覆盖都是覆盖的情况，所以差分处理后要把非0数（即监控次数）全部置为1，然后再去求所求矩形面积是否等于该范围内监控覆盖的面积即可。

代码如下：（由于n*m=10^7的数据二维数组开不了，故要把二维数据压成一维来存，注意边界的处理）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 10000050
int a[maxn];
int l,w;
//(0,0)到(i,j)的前缀和:sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
//求某个矩形的内的前缀和:s=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; 
//差分(x1,y1)到(x2,y2):a[x1][y1]+=val,a[x2+1][y1]-=val,a[x1][y2+1]-=val,a[x2+1][y2+1]+=val; 

int get_id(int i,int j)//将二维压成一维:注意下界; 
{
	if(i==0||j==0)
	{
		return 0;
	}
	else
	{
		return (i-1)*w+j;
	}
}

void div(int i,int j,int val)//差分:注意上界; 
{
	if(i>l||j>w)
	{
		return ;
	}
	else
	{
		a[get_id(i,j)]+=val;
	}
}

int main()
{
	int i,j;
	int m,q;
	while(scanf("%d%d",&l,&w)!=EOF)
	{
		scanf("%d",&m);
		int x1,y1,x2,y2;
		memset(a,0,sizeof(a));
		for(i=1;i<=m;i++)//差分; 
		{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			div(x1,y1,1);
			div(x2+1,y1,-1);
			div(x1,y2+1,-1);
			div(x2+1,y2+1,1);
		}
		for(i=1;i<=l;i++)//对元素数组进行差分的累加效应; 
		{
			for(j=1;j<=w;j++)
			{
				a[get_id(i,j)]+=a[get_id(i-1,j)]+a[get_id(i,j-1)]-a[get_id(i-1,j-1)];
			}
		}
		for(i=1;i<=l*w;i++)
		{
	        if(a[i]!=0)
	        {
	        	a[i]=1;//由于不管重不重叠,所有有覆盖的区域都设为1; 
			}
		}
		for(i=1;i<=l;i++)
		{
			for(j=1;j<=w;j++)
			{
				//求前缀和:sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; 
				a[get_id(i,j)]+=a[get_id(i-1,j)]+a[get_id(i,j-1)]-a[get_id(i-1,j-1)];
			}
		}
		scanf("%d",&q);
		for(i=1;i<=q;i++)
		{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			//s=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
			int s=a[get_id(x2,y2)]-a[get_id(x2,y1-1)]-a[get_id(x1-1,y2)]+a[get_id(x1-1,y1-1)];
			if(s==(y2-y1+1)*(x2-x1+1))
			{
				printf("YES\n");
			}
			else
			{
				printf("NO\n");
			}
		}
	}
	return 0;
}