[CF 529C] Rooks and Rectangles

作法：

首先可以推出一個矩形被保護住的充要條件：每個直行都有一個車，或是每個橫排都有一個車，因此我們可以直的做一次橫的做一次，判斷「這個矩形中是否每個直排都有車」，然後把所有的 x , y 座標交換再作一次就可以了。當在處理第 i 個詢問時，假設他的上下邊界分別為 y2 , y1 ，左右邊界為 x1 , x2 ，那麼當我們只有考慮所有 y 座標 <= y2 的車時，我們只要知道「在橫座標 x1 ~ x2 中，每個橫座標中位置最上面的車的 x 座標的最小值」，然後看他有沒有 >= y1 ，就可以知道這個矩形是否滿足條件了。因此只要按照詢問矩形的 y2 從小到大排序，維護一個可以求區間最小值的線段樹，每次把 y 座標 <= 當前詢問的 y2 座標的車都加進資料結構中，然後查詢最小值就可以了。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxn=100000+10,maxm=200000+10 ;
 
int ST[4*maxn] ;
void build()
{
    memset(ST,-1,sizeof(ST)) ;
}
 
void modify(int L,int R,int id,int pos,int val)
{
    if(L==R) { ST[id]=val ; return ; }
    int mid=(L+R)/2 ;
    if(pos<=mid) modify(L,mid,2*id,pos,val) ;
    else modify(mid+1,R,2*id+1,pos,val) ;
    ST[id]=min(ST[2*id],ST[2*id+1]) ;
}
 
int query(int l,int r,int L,int R,int id)
{
    if(l==L && r==R) return ST[id] ;
    int mid=(L+R)/2 ;
    if(r<=mid) return query(l,r,L,mid,2*id) ;
    else if(l>mid) return query(l,r,mid+1,R,2*id+1) ;
    else return min(query(l,mid,L,mid,2*id),
                    query(mid+1,r,mid+1,R,2*id+1)) ;
}
 
struct P
{
    int x1,y1,x2,y2,id ;
    void get(int _id)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ;
        id=_id ;
    }
    bool operator < (const P &rhs) const
    {
        return x2<rhs.x2 ;
    }
}q[maxm];
 
int ans[maxm] ;
pii a[maxm] ;
void solve(int n,int m,int k,int Q)
{
    build() ;
    for(int i=1,j=1;i<=Q;i++)
    {
        while(j<=k && a[j].F<=q[i].x2)
            modify(1,m,1,a[j].S,a[j].F) , j++ ;
        if(query(q[i].y1,q[i].y2,1,m,1)>=q[i].x1)
            ans[q[i].id]=1 ;
    }
}
 
main()
{
    int n,m,k,Q ;
    scanf("%d%d%d%d",&n,&m,&k,&Q) ;
    for(int i=1;i<=k;i++) scanf("%d%d",&a[i].F,&a[i].S) ;
    for(int i=1;i<=Q;i++) q[i].get(i) ;
    sort(q+1,q+Q+1) ;
    sort(a+1,a+k+1) ;
    solve(n,m,k,Q) ;
 
    swap(n,m) ;
    for(int i=1;i<=k;i++) swap(a[i].F,a[i].S) ;
    for(int i=1;i<=Q;i++)
        swap(q[i].x1,q[i].y1) , swap(q[i].x2,q[i].y2) ;
    sort(q+1,q+Q+1) ;
    sort(a+1,a+k+1) ;
    solve(n,m,k,Q) ;
    for(int i=1;i<=Q;i++) printf("%s\n",ans[i]?"YES":"NO") ;
}