题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6514
题目大意
给定一个二维平面范围,
和p个监视区,q个偷盗区,
监视区和偷盗区形状是矩形,
q个询问问偷盗区是否被监控去完全覆盖.
题目分析
二维差分,蛮套路的,
如果知道一维的情况那么二维不难,
比如(x,y),(p,q)给定这两个坐标点,
那么我们要想让这个矩形区域全置1,
把(x,y),(p+1,q+1)打上1的标记,
(x,q+1),(p+1,y)打上-1的标记,
然后做二维前缀和即可,
为了方便统计查询,再做一次前缀和,
查询时判断个数关系即可.
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=1e7+100;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意:
给定一个二维平面范围,
和p个监视区,q个偷盗区,
监视区和偷盗区形状是矩形,
q个询问问偷盗区是否被监控去完全覆盖.题目分析:
二维差分,蛮套路的,
如果知道一维的情况那么二维不难,
比如(x,y),(p,q)给定这两个坐标点,
那么我们要想让这个矩形区域全置1,
把(x,y),(p+1,q+1)打上1的标记,
(x,q+1),(p+1,y)打上-1的标记,
然后做二维前缀和即可,
为了方便统计查询,再做一次前缀和,
查询时判断个数关系即可.
*/
int n,m,pp,qq;
ll a[maxn];
int s(int x,int y){return x*m+y-1;
}
int main(){while(scanf("%d%d",&n,&m)!=EOF){rep(i,0,n+1) rep(j,0,m+1) a[s(i,j)]=0;scanf("%d",&pp);rep(i,0,pp){int x,y,p,q;scanf("%d%d%d%d",&x,&y,&p,&q);a[s(x,y)]++,a[s(p+1,q+1)]++;a[s(x,q+1)]--,a[s(p+1,y)]--; }rep(i,1,n+1) rep(j,1,m+1) a[s(i,j)]+=a[s(i-1,j)]+a[s(i,j-1)]-a[s(i-1,j-1)]; rep(i,1,n+1) rep(j,1,m+1) a[s(i,j)]=min(a[s(i,j)],1LL);rep(i,1,n+1) rep(j,1,m+1) a[s(i,j)]+=a[s(i-1,j)]+a[s(i,j-1)]-a[s(i-1,j-1)]; scanf("%d",&qq);rep(i,0,qq){int x,y,p,q;scanf("%d%d%d%d",&x,&y,&p,&q);if((1LL*(p-x+1)*(q-y+1))==(a[s(p,q)]-a[s(p,y-1)]-a[s(x-1,q)]+a[s(x-1,y-1)]))puts("YES");else puts("NO");}}return 0;
}