1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 #include<string> 6 7 using namespace std; 8 const int maxn = 1e7 + 10; 9 10 int n, m, p, q; 11 int diff[maxn]; 12 int sum[maxn]; 13 14 void init() 15 { 16 for(int i = 0 ; i < maxn ; i++){ 17 diff[i] = sum[i] = 0; 18 } 19 } 20 21 int tsf(int x,int y)//压维 22 { 23 return (x - 1) * m + y; 24 } 25 26 int main(){ 27 while(~scanf("%d%d",&n,&m)){ 28 init(); 29 scanf("%d",&p); 30 int x1,y1,x2,y2; 31 for(int i = 1 ; i <= p ; i++){ 32 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 33 diff[tsf(x1, y1)]++; 34 if(y2 + 1 <= m){ 35 diff[tsf(x1, y2+1)]--; 36 } 37 if(x2 + 1 <= n){ 38 diff[tsf(x2+1, y1)]--; 39 } 40 if(x2 + 1 <= n && y2 + 1 <= m){ 41 diff[tsf(x2+1, y2+1)]++; 42 } 43 }//二维差分 44 45 for(int i = 1 ; i <= n ; i++){ 46 for(int j = 1 ; j <= m ; j++){ 47 if(i - 1 > 0) 48 diff[tsf(i, j)] += diff[tsf(i - 1, j)]; 49 if(j - 1 > 0) 50 diff[tsf(i, j)] += diff[tsf(i, j - 1)]; 51 if(i > 1 && j > 1) 52 diff[tsf(i, j)] -= diff[tsf(i - 1, j - 1)];//求差分的前缀和，确定各点的原数值 53 54 if(diff[tsf(i, j)] > 0){//判断是否有摄像机覆盖 55 sum[tsf(i, j)] = 1; 56 }else{ 57 sum[tsf(i, j)] = 0; 58 } 59 60 if(i - 1 > 0)//求原数组的前缀和，sum[i][j]表示原点与该点围成的矩形内有多少个可观测点 61 sum[tsf(i, j)] += sum[tsf(i - 1, j)]; 62 if(j - 1 > 0) 63 sum[tsf(i, j)] += sum[tsf(i, j - 1)]; 64 if(i > 1 && j > 1) 65 sum[tsf(i, j)] -= sum[tsf(i - 1, j - 1)]; 66 } 67 } 68 69 scanf("%d",&q); 70 for(int i = 1 ; i <= q ; i++){ 71 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 72 int s = (y2 - y1 + 1) * (x2 - x1 + 1); 73 int cnt = sum[tsf(x2, y2)];//容斥原理 74 if(x1 - 1 > 0) cnt -= sum[tsf(x1-1, y2)]; 75 if(y1 - 1 > 0) cnt -= sum[tsf(x2, y1-1)]; 76 if(x1 - 1 > 0 && y1 - 1 > 0) cnt += sum[tsf(x1-1, y1-1)]; 77 78 if(s == cnt){ 79 printf("YES "); 80 }else{ 81 printf("NO "); 82 } 83 } 84 } 85 86 return 0; 87 }
对初入门是很好的一道题
网上的大多数题解用了vector但似乎缺少了灵魂
本题压维反正不难
关键点在于理解二维差分、二维前缀和之间的联系
加油
这两篇感觉挺不错的 推荐一下
参考：
https://www.cnblogs.com/i-cookie/p/11517651.html
https://www.cnblogs.com/LMCC1108/p/10753451.html