HDU---6514：Monitor（二维差分）

题意：

给你N个监控器，每个监控器的监控范围都是一个矩形，再给出Q个查询，问查询的矩形是否被完全监控

分析：

二维差分：

和一维差分有异曲同工之处，如果我们想把左上角(x1，y1)，右下角(x2,y2)的矩形中的每一格+1，先标记a[x1][y1] +=1，a[x1][y2+1] -= 1，a[x2+1][y1] -= 1，a[x2+1][y2+1] += 1；最后再求一遍二维前缀和即可得到每个格子变化的值

二维前缀和：

定义a[x][y] 为左上角(1，1)，右下角为(x，y)的矩形中的元素和，那么a[x][y] += a[x][y-1] + a[x-1][y] - a[x-1][y-1]，即可得到a[x][y]

此题得到每个格子变化的值后，对于大于1的值令其等于1，再求一遍二维前缀和，a[x][y]的值就代表左上角(1，1)，右下角(x，y)的矩形中有多少个格子被监控了，最后询问时判断查询的矩形的值是否等于它的面积即可

代码：

#include <vector>
#include <cstdio>
#include <iostream>

using namespace std;
int n,m,q,p,x1,yy1,x2,y2;
int main(){
    while(~scanf("%d %d",&n,&m)){
        vector<vector<int> > a(n+10,vector<int>(m+10));
        scanf("%d",&p);
        while(p--){
            scanf("%d %d %d %d",&x1,&yy1,&x2,&y2);
            a[x1][yy1] ++;
            a[x2+1][yy1] --;
            a[x1][y2+1] --;
            a[x2+1][y2+1]++;
        }
        for(int i = 1; i <= n; ++i)
            for(int j = 1;j <= m; ++j)
                a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        for(int i = 1; i <= n; ++i){
            for(int j = 1;j <= m; ++j){
                if(a[i][j]) a[i][j] = 1;
                a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
            }
        }
        scanf("%d",&q);
        while(q--){
            scanf("%d %d %d %d",&x1,&yy1,&x2,&y2);
            if(a[x2][y2]-a[x1-1][y2]-a[x2][yy1-1]+a[x1-1][yy1-1]==(x2-x1+1)*(y2-yy1+1)) puts("YES");
            else puts("NO");
        }    
    }
    return 0;
}