题解 P4793 【[AHOI2008]矩形藏宝地】

· · 题解

放一篇（可能）比较正常的cdq题解

题解：

题意显然是一个四维偏序，然而三只log的复杂度也显然是不优秀的

注意到题目只是让我们判定某个矩形能否被其他某一个矩形包括，而不是有几对关系，因此本题可以通过某些方法简化掉一层限制

考虑若矩形j要对矩形i产生贡献，即j包含i，需要满足x_{j2}>x_{i2}，y_{j2}>y_{i2}，x_{j1}<x_{i1}，y_{j1}<y_{i1}

假设我们此时已经用排序+分治干掉前两维了，j此时一定会排在i的前面，可以想象一下i的右上角已经被所有在区间[l,p]中的矩形的右上角包住了（p是合并时的左指针，能保证其中一层限制），现在只需要判定这部分的矩形的左下角能否包住i的左下角就好了

由于这是连贯且起始点是定值的区间，我们对他们记一个前缀min，看看对于某个点的左半边，有没有还比他低的点，这些点就是在它的左下角的了，在满足包住右上角的同时也能包住左下角，于是就可以判定矩形i能被另外某个矩形包住了

前缀min是树状数组的一个经典应用，可以log解决

最后统计一下有几个矩形能被包住就是答案

另外还有一个小细节，为了优化大坐标带来的复杂度冗余，我们可以先对横纵坐标离散化一下

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

#define dc divide_and_conquer
#define xn XN
#define yn YN

const int N=2e5+5;
int ans,xn,yn,numx[N<<1],numy[N<<1],tr[N<<1],n;

struct dc{
    int x,y,xx,yy,ans;
    inline bool operator < (const dc &nt) const{ //先按右上角的x排
        return xx>nt.xx;
    }
}a[N],b[N];

#define lowbit(x) (x&(-x))

void clear(int x){ //重新赋回无穷大
    while(x<=xn){
        tr[x]=0x3f3f3f3f;
        x+=lowbit(x);
    }
}

void up(int x,int v){ //修改
    while(x<=xn){
        tr[x]=min(tr[x],v);
        x+=lowbit(x);
    }
}

int que(int x){ //查询
    int res=0x3f3f3f3f;
    while(x){
        res=min(res,tr[x]);
        x-=lowbit(x);
    }
    return res;
}

void cdq(int l,int r){
    if(l==r) return ;
    int mid=l+r>>1;
    cdq(l,mid);cdq(mid+1,r);
    int p=l,q=mid+1,i=l-1;
    while(p<=mid&&q<=r){
        if(a[p].yy>a[q].yy){ //满足右上角能包住
            up(a[p].x,a[p].y); //维护下前缀最小
            b[++i]=a[p++];
        }
        else{
            if(que(a[q].x)<a[q].y) a[q].ans=1; //若它的前面还有比他低的，就是被包住了
            b[++i]=a[q++];
        }
    }
    while(q<=r){
        if(que(a[q].x)<a[q].y) a[q].ans=1;
        b[++i]=a[q++];
    }
    for(int i=l;i<p;i++) clear(a[i].x); //复原树状数组
    while(p<=mid) b[++i]=a[p++];
    for(int i=l;i<=r;i++) a[i]=b[i];
}

signed main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i].x);numx[++xn]=a[i].x;
        read(a[i].y);numy[++yn]=a[i].y;
        read(a[i].xx);numx[++xn]=a[i].xx;
        read(a[i].yy);numy[++yn]=a[i].yy;
    }
    memset(tr,0x3f,sizeof tr); //初始赋无穷大
    sort(numx+1,numx+1+xn);
    sort(numy+1,numy+1+yn);
    for(int i=1;i<=n;i++){
        a[i].x=lower_bound(numx+1,numx+1+xn,a[i].x)-numx; //离散坐标
        a[i].y=lower_bound(numy+1,numy+1+yn,a[i].y)-numy;
        a[i].xx=lower_bound(numx+1,numx+1+xn,a[i].xx)-numx;
        a[i].yy=lower_bound(numy+1,numy+1+yn,a[i].yy)-numy;
    }
    sort(a+1,a+1+n);
    cdq(1,n);
    for(int i=1;i<=n;i++) ans+=a[i].ans; //统计答案
    write(ans);
}