HDU - 6514 Monitor(二维差分)

题目链接：点击查看

题目大意：给出一个n*m的矩阵，开始全部初始化为0，然后给出一系列的小矩阵的范围，小矩阵中的格子全部变为1，最后再给出一些查询，查询矩阵范围内是否所有的格子都是1，是的话输出yes，否则输出no

题目分析：二维差分+二维前缀和，

这里放一篇个人觉得不错的差分博客：点击查看

然后二维前缀和不多赘述了，很早之前就已经掌握了的知识了。

因为初始化全部为0，我们在将一系列的小矩阵变为1的过程中，并不需要全部变为1，只需要将对角线上的点分别赋值表示差分即可，等操作完毕后，对差分的数组求一下前缀和，这个时候每个点(i,j)所表示的值，是该点相对于0来说变化了多少，在这个题目中，我们可以保证每个点的值都是大于等于零的，因为在区间内的操作都是只加不减，随后将每个点的值都改成0或1，原先大于等于1的全部变为1即可，再求一次前缀和，这个时候输入区间后只需要判断区间的大小（即面积）和前缀和是否相等就好了

代码简洁，直接上代码了：

#include<iostream>
#include<cstdio> 
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<sstream>
using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const int N=1e7+100;

int a[N];

int n,m;

int getid(int i,int j)
{
	if(i==0||j==0||i>n||j>m)//考虑越界情况，如果越界返回0，因为a[0]正常情况下是访问不到的，所以让他一直等于0即可
		return 0;
	return (i-1)*m+j;
}

void update(int i,int j,int val)
{
	if(getid(i,j)==0)//如果越界就不需要更新了
		return;
	a[getid(i,j)]+=val;
}

int main()
{
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				a[getid(i,j)]=0;
		int t;
		scanf("%d",&t);
		while(t--)
		{
			int x,y,xx,yy;
			scanf("%d%d%d%d",&x,&y,&xx,&yy);//维护差分区间
			update(x,y,1);
			update(xx+1,yy+1,1);
			update(x,yy+1,-1);
			update(xx+1,y,-1);
		}
		for(int i=1;i<=n;i++)//前缀和
			for(int j=1;j<=m;j++)
				a[getid(i,j)]+=a[getid(i-1,j)]+a[getid(i,j-1)]-a[getid(i-1,j-1)];
		for(int i=1;i<=n;i++)//转换为0和1
			for(int j=1;j<=m;j++)
				a[getid(i,j)]=a[getid(i,j)]?1:0;
		for(int i=1;i<=n;i++)//前缀和
			for(int j=1;j<=m;j++)
				a[getid(i,j)]+=a[getid(i-1,j)]+a[getid(i,j-1)]-a[getid(i-1,j-1)];
		scanf("%d",&t);
		while(t--)
		{
			int x,y,xx,yy;
			scanf("%d%d%d%d",&x,&y,&xx,&yy);
			int temp1=(xx-x+1)*(yy-y+1);//区间大小
			int temp2=a[getid(xx,yy)]-a[getid(xx,y-1)]-a[getid(x-1,yy)]+a[getid(x-1,y-1)];//前缀和大小
			if(temp1==temp2)
				cout<<"YES"<<endl;
			else
				cout<<"NO"<<endl;	
		}
	}
	
	
	
	
	 
	 
	
	
	
	
	return 0;
}