HDU - 6514 Monitor(二维差分)
程序员文章站
2022-07-12 17:38:26
...
题目链接:点击查看
题目大意:给出一个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;
}