分析：运用扫描线，先从左到右扫描，用纵坐标进行建树，
随着扫描线的右向右移动。不断更新横坐标小于扫描线的车
更新的时候 在树中更新车的纵坐标的位置，把该位置的值变成该车的横坐标
线段树维护的是区间最大值和最小值
这样每到一个矩形区域的右边界，查询该区间的纵坐标区间内的最大值和最小值
如果最大值小于右边界，最小值大于左边界
那么这个矩形区域内每一行都可以被矩形区域内的车覆盖，标记一下
同理，从下到上扫描，可以找到符合条件的矩形
#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> using namespace std; typedef long long LL; const int N=2e5+5; int n,m,k,q; struct Rec { int x1,x2,y1,y2,id; bool operator<(const Rec &e)const { return x2<e.x2; } } o[N]; bool cmp1(Rec a,Rec b) { return a.x2<b.x2; } bool cmp2(Rec a,Rec b) { return a.y2<b.y2; } struct Point { int x,y; } p[N]; bool cmp3(Point a,Point b) { return a.x<b.x; } bool cmp4(Point a,Point b) { return a.y<b.y; } int c[N<<1],b[N<<1]; void build(int rt,int l,int r) { b[rt]=c[rt]=N; if(l==r)return; int mid=(l+r)>>1; build(rt*2,l,mid); build(rt*2+1,mid+1,r); } void pushup(int rt) { c[rt]=min(c[rt*2],c[rt*2+1]); b[rt]=max(b[rt*2],b[rt*2+1]); } void update(int rt,int l,int r,int pos,int t) { if(l==r) { b[rt]=c[rt]=t; return; } int mid=(l+r)>>1; if(pos<=mid)update(rt*2,l,mid,pos,t); else update(rt*2+1,mid+1,r,pos,t); pushup(rt); } int querymin(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) return c[rt]; int res=N; int mid=(l+r)>>1; if(x<=mid)res=min(res,querymin(rt*2,l,mid,x,y)); if(y>mid)res=min(res,querymin(rt*2+1,mid+1,r,x,y)); return res; } int querymax(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) return b[rt]; int res=-1; int mid=(l+r)>>1; if(x<=mid)res=max(res,querymax(rt*2,l,mid,x,y)); if(y>mid) res=max(res,querymax(rt*2+1,mid+1,r,x,y)); return res; } bool ans[N]; int main() { scanf("%d%d%d%d",&n,&m,&k,&q); for(int i=1; i<=k; ++i) scanf("%d%d",&p[i].x,&p[i].y); for(int i=1; i<=q; ++i) scanf("%d%d%d%d",&o[i].x1,&o[i].y1,&o[i].x2,&o[i].y2),o[i].id=i; sort(p+1,p+1+k,cmp3); sort(o+1,o+1+q,cmp1); int cnt=1; build(1,1,m); for(int i=1; i<=q; ++i) { for(; cnt<=k&&p[cnt].x<=o[i].x2; ++cnt) update(1,1,m,p[cnt].y,p[cnt].x); int a1=querymin(1,1,m,o[i].y1,o[i].y2); int a2=querymax(1,1,m,o[i].y1,o[i].y2); if(a1>=o[i].x1&&a2<=o[i].x2) ans[o[i].id]=1; } sort(p+1,p+k+1,cmp4); sort(o+1,o+1+q,cmp2); build(1,1,n),cnt=1; for(int i=1; i<=q; ++i) { for(; cnt<=k&&p[cnt].y<=o[i].y2; ++cnt) update(1,1,n,p[cnt].x,p[cnt].y); int a1=querymin(1,1,n,o[i].x1,o[i].x2); int a2=querymax(1,1,n,o[i].x1,o[i].x2); if(a1>=o[i].y1&&a2<=o[i].y2) ans[o[i].id]=1; } for(int i=1; i<=q; ++i) if(ans[i])printf("YES "); else printf("NO "); return 0; }