您的位置: 首页  >  IT文章  >  HDU-6514 Monitor（二维前缀和+差分）

HDU-6514 Monitor（二维前缀和+差分）

分类: IT文章 • 2022-04-20 12:27:28

http://acm.hdu.edu.cn/showproblem.php?pid=6514

Problem Description

Xiaoteng has a large area of land for growing crops, and the land can be seen as a rectangle of q times of crops. he also guessed the range they were going to steal, which was also a rectangle. Xiao Teng wants to know if his monitors can see all the thieves at a time.

Input

There are mutiple test cases.
Each case starts with a line containing two integers ),meaning the lower left corner and upper right corner of the rectangle.

Output

For each case you should print q lines.
Each line containing YES or NO mean the all thieves whether can be seen.

Sample Input

6 6
3
2 2 4 4
3 3 5 6
5 1 6 2
2
3 2 5 4
1 5 6 5

Sample Output

YES
NO

Hint

In the picture,the red solid rectangles mean the monitor Xiaoteng installed, and the blue dotted rectangles mean the area will be stolen.

HDU-6514 Monitor（二维前缀和+差分）

 (x1,y1)为矩形左下角,(x2,y2)为矩形右下角，竖直向上为x正方向，水平向右为y正方向

 HDU-6514 Monitor（二维前缀和+差分）

题意：

在一个面积不超过n*m的矩形上，有p个矩形A，问之后的q个矩形B能否被之前的A全部覆盖。

思路：

由于n*m,p,q的范围过大，于是考虑O(n*m+p+q)的做法，即二维前缀和+差分。

对于A类矩形(x1,y1,x2,y2)，我们只需要在(x1,y1),(x2+1,y2+1)处+1，在(x1,y2+1),(x2+1,y1)处-1 ，

之后对整个面积求一个前缀和，则大于0的地方就是被A类矩形覆盖的点。

把值大于0的地方变成1，再一次求一次前缀和，处理好后即可在O(1)的时间算出一个矩形内被覆盖的点的数量。
（详细见注释）

亮点：

二维数组化为一维

两次求前缀和，重新赋值

代码如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <math.h>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 //const double PI=acos(-1);
17 const int maxn=1e7+10;
18 using namespace std;
19 
20 int a[maxn];//二维化为一维 
21 int n,m;
22 
23 void Add(int x,int y,int val)//添加标记 
24 {
25     if(x>n||y>m)
26         return;
27     a[(x-1)*m+y]+=val;
28 }
29 
30 int Query(int x,int y)//得到该处的值，主要用来处理边界0 
31 {
32     if(x==0||y==0)
33         return 0;
34     return a[(x-1)*m+y];
35 }
36 
37 void Sum()//求前缀和 
38 {
39     for(int i=1;i<=n;i++)
40     {
41         for(int j=1;j<=m;j++)
42         {
43             a[(i-1)*m+j]+=Query(i,j-1)+Query(i-1,j)-Query(i-1,j-1);
44         }
45     }
46 }
47 
48 int main()
49 {
50     while(~scanf("%d %d",&n,&m))
51     {
52         memset(a,0,sizeof(a));
53         int x1,x2,y1,y2;
54         int p,q;
55         scanf("%d",&p);
56         while(p--)
57         {
58             scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
59             Add(x1,y1,1);
60             Add(x2+1,y2+1,1);
61             Add(x1,y2+1,-1);
62             Add(x2+1,y1,-1);
63         }
64         Sum();//第一次求二维前缀和，a[i]>0说明该处被覆盖过 
65         for(int i=1;i<=n;i++)//将被覆盖的点重新赋值为1，便于判断 
66         {
67             for(int j=1;j<=m;j++)
68             {
69                 if(a[(i-1)*m+j])
70                     a[(i-1)*m+j]=1;
71             }
72         }
73         Sum();//第二次求前缀和，得到的结果即为矩形内被染色的面积 
74         scanf("%d",&q);
75         while(q--)
76         {
77             scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
78             int ans=Query(x2,y2)-Query(x1-1,y2)-Query(x2,y1-1)+Query(x1-1,y1-1);//利用前缀和得出矩形内被染色的面积 
79             if(ans==(x2-x1+1)*(y2-y1+1))//看染色的面积是否等于矩形的总面积 
80                 printf("YES
");
81             else
82                 printf("NO
");
83         }
84     }
85     return 0;
86 }

相关推荐