HDU 6514 Monitor(二维差分+前缀和)

题目链接: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;
}