Monitor HDU 6514 二维差分入门学习
题意
小腾有\(n*m\)的田地，但是有小偷来偷东西，在一片矩形区域上，有一部分区域是监控可以覆盖到的，这部分区域由一个或多个包含于该矩形区域的小矩形构成；现在给你另一个包含在该矩形区域的小矩形A，问你这个小矩形能否被监控完全覆盖。
解题思路
这个题可以模拟做，就是开一个二维数组，把能监控的区域标记为1，否者就是0，然后在给的小矩形内看看这里面1的个数已不是等于小矩形的面积，是的话就是YES，否者就是NO。但是这个方法会超时。我就无能为力了，这时旁白同学说这个题得用二维差分来做（还没学过），神奇，我就找了个博客，有位大佬正好写了这道题，而且很详细，易懂，点我进来。
这里我就补充一下自己看过这个博客后的一点见解。
- 这里建立二维数组，坐标不用像大佬所说的那样转换，就正常那样就行，二维数组可以正常表示，不用把左下改为左上，右上改为右下，这里可能是那位作者想错了。
- 这里需要使用vector来建立二维数组，要不然会爆，而这里如何用vector来建立二维数组我还真不会，下面代码里见（这个也很重要）。
- 感觉差分就是树状数组的简洁版。
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1e7+7;
int n, m, p, q;
int main()
{
int x1, y1, x2, y2;
while(scanf("%d%d", &n, &m)!=EOF)
{
vector< vector<int> > recode(n+2, vector<int>(m+2)), glass(n+2, vector<int>(m+2));
//这里n+2代表第一维的参量，第二个是代表第二维
//这样声明vector后就可以直接使用recode[i][j],只要在范围内就行
//如果使用vector<int> recode[maxm],我们不能直接使用比如recode[2][3]，
//因为可能在recode[2][3]之前，并没有数字存储。
scanf("%d", &p);
for(int i=1; i<=p; i++)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
recode[x1][y1]++;
recode[x2+1][y2+1]++;
recode[x1][y2+1]--;
recode[x2+1][y1]--;
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
recode[i][j]+=recode[i-1][j]+recode[i][j-1]-recode[i-1][j-1];
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
glass[i][j]+=glass[i-1][j]+glass[i][j-1]-glass[i-1][j-1] + ( recode[i][j]>0? 1:0);
}
}
scanf("%d", &q);
while(q--)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int eara=glass[x2][y2]-glass[x2][y1-1]-glass[x1-1][y2]+glass[x1-1][y1-1];
if(eara==(x2-x1+1)*(y2-y1+1))
{
printf("YES\n");
}
else printf("NO\n");
}
}
return 0;
}