http://acm.hdu.edu.cn/showproblem.php?pid=6514
题意
给出一个大矩形((nmleq10^7)),有p个矩形覆盖,然后有q次询问,询问指定矩形内是否覆盖完全
题解
扫描线?- 因为不用修改,所以差分前缀和就好,注意重复覆盖点需要重新赋值
- (n*m leq 10^7),二维数组一维化,一维化后一定要严格判边界,不然会导致访问混乱
代码
#include<bits/stdc++.h>
using namespace std;
int a[20000000],n,m,X1,X2,Y1,Y2,q;
int id(int x,int y){
return x*(m+1)+y;
}
void ud(int x,int y,int v){
if(x>n||y>m)return;
int p=id(x,y);
a[p]+=v;
}
int qy(int x,int y){
return a[id(x,y)];
}
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)a[id(i,j)]=0;
scanf("%d",&q);
while(q--){
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
ud(X1,Y1,1);ud(X2+1,Y1,-1);ud(X1,Y2+1,-1);
ud(X2+1,Y2+1,1);
}
/*cout<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){cout<<a[id(i,j)]<<" ";}
cout<<endl;
}*/
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[id(i,j)]+=a[id(i-1,j)]+a[id(i,j-1)]-a[id(i-1,j-1)];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[id(i,j)])a[id(i,j)]=1;
//cout<<a[id(i,j)]<<" ";
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[id(i,j)]+=a[id(i-1,j)]+a[id(i,j-1)]-a[id(i-1,j-1)];
}
}
scanf("%d",&q);
while(q--){
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
int tp=a[id(X2,Y2)]-a[id(X2,Y1-1)]-a[id(X1-1,Y2)]+a[id(X1-1,Y1-1)];
if(tp==(X2-X1+1)*(Y2-Y1+1))puts("YES");
else puts("NO");
}
}
}