P7865 「EVOI-RD1」无人机航拍（ ( [主题训练B1]线段树 ) 第四题）[ 采用高级二维差分数组 ]
题目背景
T 市举行活动需要拍摄高空俯瞰图，找来了一个无人机机队负责拍摄工作。 一E孤行 是队伍的队长，他根据广场的规模来安排无人机的位置。
题目描述
有一个广场，可以看做是一个 𝑛×𝑚 的矩形；一E孤行 一共有 𝑠 架无人机，每架无人机的拍摄范围也可以看做是一个矩形，无人机机队的拍摄范围为所有无人机拍摄范围的并。
一E孤行 负责安排无人机的位置，而总负责人 WuuTue 要验收她他的方案。WuuTue 的验收方法是列举出 𝐿 个重要的区域，每个重要区域也是一个矩形。 一E孤行 方案的优秀程度取决于有多少个重要区域完全在无人机机队的拍摄范围中。
因此，对于每一个重要区域， 一E孤行 想知道它是否完全在无人机机队的拍摄范围中。
输入格式
第一行，用空格隔开的两个整数 𝑛 和 𝑚，用来描述广场的大小。
第二行，一个整数 𝑠，表示无人机队伍中无人机的总数量。
第三行到第 𝑠+2 行，每行四个用空格隔开的整数，𝑎1,𝑏1,𝑎2,𝑏2，用来描述一架无人机的拍摄范围。其中 𝑎1,𝑏1 表示矩形的左下角坐标，𝑎2,𝑏2 表示右上角的坐标。
第 𝑠+3 行，一个整数 𝐿，表示活动总负责人列出的重要区域的数量 𝐿。
最后 𝐿 行，每行四个用空格隔开的整数 𝑟1,𝑐1,𝑟2,𝑐2，用来描述一个重要区域。其中 𝑟1,𝑐1 表示矩形区域左下角坐标，𝑟2,𝑐2 表示右上角坐标。
输出格式
输出 𝐿 行，对于每个重要区域，如果完全在机队的拍摄范围内就输出 Yes，否则出 No。每个答案占一行。
输入输出样例
输入 #1
9 9
3
2 1 4 4
2 5 4 9
5 2 7 6
2
3 3 6 6
5 6 8 8输出 #1
Yes
No说明/提示
样例说明
如下图所示，区域 𝐴,𝐵,𝐶 分别是某某安排的无人机能够覆盖的范围，区域 𝐷,𝐸 是 WuuTue 要验收时列举的重点区域，区域 𝐷 能够被完全覆盖，区域 𝐸 不能被全部覆盖。
数据规模与约定
本题采用捆绑测试。
对于 40% 的数据：1≤𝑛≤1000，1≤𝑠≤100 。
对于 100% 的数据：
- 1≤𝑛,𝑚≤3×
。
- 1≤𝑠,𝐿≤
。
- 1≤𝑥1<𝑥2≤𝑛。
- 1≤𝑟1<𝑟2≤𝑛。
- 1≤𝑦1<𝑦2≤𝑚。
- 1≤𝑐1<𝑐2≤𝑚。
-
参考代码：【可以采用二维线段树，但此题数据可以建立二维数组，用二维差分数组更简便】
-
#include<bits/stdc++.h> using namespace std; const int N=3e3+5; int p,l,n,m,sum[N][N],a,b,c,d,m1[N][N]; int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; cin>>p; for(int i=1;i<=p;i++) { cin>>a>>b>>c>>d; sum[a][b]++;//建立二维差分数组 sum[c+1][b]--; sum[c+1][d+1]++; sum[a][d+1]--; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];//sum数组储存当前格子所占矩阵的个数 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) m1[i][j]=m1[i-1][j]+m1[i][j-1]-m1[i-1][j-1]+(sum[i][j]>0?1:0);//统计当前前缀和即矩阵面积 // cout<<'\n'; // for(int i=n;i>=1;i--) // { // for(int j=1;j<=m;j++) // cout<<m1[i][j]<<" "; // cout<<'\n'; // } cin>>l; for(int i=1;i<=l;i++) { cin>>a>>b>>c>>d; int h=m1[c][d]-m1[a-1][d]-m1[c][b-1]+m1[a-1][b-1]; // cout<<h<<'\n'; if(h==(c-a+1)*(d-b+1))//看无人机覆盖面积是否等于要求矩阵的面积 cout<<"Yes"<<'\n'; else//不行，输出no cout<<"No"<<'\n'; } return 0; }