自动搬运

查看原文

来自洛谷，原作者为

	冷月葬T魂 I solemnly swear that I am up to no good

搬运于2025-08-24 22:33:47，当前版本为作者最后更新于2021-08-12 11:51:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先可以发现 $n,m$ 较小，故考虑将无人机能覆盖的所有格子记录在一个二维数组 $a$ 中。
具体来说，将每个无人机覆盖的范围 $(x_1,y_1,x_2,y_1)$ 分解为两个“事件”：“开始覆盖”$(x_1,y_1,y_2,1)$ 和 “结束覆盖”$(x_2+1,y_1,y_2,-1)$。然后将所有事件按 $x$ 排序，用扫描线算法，维护一个树状数组 $T$，记录当前 $x$ 一行（或列，看你怎么理解坐标 $(x,y)$）中哪些方格被覆盖，依次处理每个事件，由于 $x$ 变化的总数为 $n$，故这一步的时间复杂度为 $O(nm \log m)$。
然后预处理出二维数组 $a$ 的二维前缀和，对于每个询问，判断 $a$ 中对应子矩阵的元素和是否等于询问的总面积即可（这等价于 $a$ 中对应子矩阵的每个元素都是 $1$，注意 $a$ 中存储的是格子是否被覆盖而不是覆盖多少次）。

代码如下：

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,v) memset(a,v,sizeof(a))
//#define int long long
using namespace std;

const int N=3e3+5,M=2e6+5;

class FTree{
	int n,c[N*4];
	int lowbit(int x)
	{
		return x&(-x);
	}
public:
	void init(int _n)
	{
		n=_n;
		clr(c,0);
	}
	void poke(int p,int x)
	{
		while(p<=n){
			c[p]+=x;
			p+=lowbit(p);
		}
	}
	int peek(int p)
	{
		int res=0;
		while(p){
			res+=c[p];
			p-=lowbit(p);
		}
		return res;
	}
};

struct cpdd{
	int x,y1,y2,type;
	bool operator< (const cpdd& cp) const
	{
		return x<cp.x;
	}
}cp[M];

int n,m,s,a[N][N],sum[N][N];
FTree T;

int area(int x1,int y1,int x2,int y2)
{
	return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}

inline int read()
{
	register char Charlie;
	while((Charlie=getchar())<'0'||Charlie>'9') ;
	register int Vinnie=Charlie-'0';
	while((Charlie=getchar())>='0'&&Charlie<='9') Vinnie=(Vinnie<<3)+(Vinnie<<1)+Charlie-'0';
	return Vinnie;
}

signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	
//	cin>>n>>m;
	n=read();
	m=read();
	
//	cin>>s;
	s=read();
	For(i,1,s){
		int x1,y1,x2,y2;
//		cin>>x1>>y1>>x2>>y2;
		x1=read();
		y1=read();
		x2=read();
		y2=read();
		cp[i*2-1]=(cpdd){x1,y1,y2,1};
		cp[i*2]=(cpdd){x2+1,y1,y2,-1};
	}
	
	sort(cp+1,cp+1+s*2);
	
	int cur=1;
	
	T.init(m+1);
	
	For(i,1,s*2){
		while(cur<cp[i].x){
			For(j,1,m){
				a[cur][j] = T.peek(j)>0 ? 1 : 0;
			}
			cur++;
		}
		if(cp[i].type==1){
			T.poke(cp[i].y1,1);
			T.poke(cp[i].y2+1,-1);
		}
		else{
			T.poke(cp[i].y1,-1);
			T.poke(cp[i].y2+1,1);
		}
	}
	
	while(cur<=n){
		For(j,1,m){
			a[cur][j] = T.peek(j)>0 ? 1 : 0;
		}
		cur++;
	}
	
//	For(i,1,n){
//		For(j,1,m){
//			if(a[i][j]) cout<<'#';
//			else cout<<'.';
//		}
//		cout<<endl;
//	}
//	cout<<endl;
	
	For(i,1,n){
		For(j,1,m){
			sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];
		}
	}
	
	int Q;
//	cin>>Q;
	Q=read();
	
	while(Q--){
		int x1,y1,x2,y2;
//		cin>>x1>>y1>>x2>>y2;
		x1=read();
		y1=read();
		x2=read();
		y2=read();
		if(area(x1,y1,x2,y2)==(x2-x1+1)*(y2-y1+1)) puts("Yes");
		else puts("No");
	}
	
	return 0;
}