[AHOI2008]矩形藏宝地

kd-treeTLE成88分时, 看到大佬们用的都是cdq分治, 于是写来一篇靠特判才能过的kd-tree题解

我们可以将一个矩形(x1,y1,x2,y2), 看成是三维空间中的一个坐标为(x1,y1,x2), 点权是y2的点

那么如何判断一个矩形被包含?

对于一个矩形(x1,y1,x2,y2)

当三维空间中(0~x1-1, 0~y1-1, x2+1~\(\infty\))最大点权大于y2时, 说明该矩形被覆盖

考虑到当区域中的最大值小于y2时, 不对答案造成贡献, 因此可以大幅剪枝并获得88分的好成绩

加个O2, 第三个点判判判就能过了╮(￣▽￣)╭

#include<iostream>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    return x*f;
}
const int N=2e5+28;
int D,yi;
class KD_TREE{
private:
public:
    struct POS{
    int d[3],mx[3],mn[3],ls,rs,val,num;
    inline int &operator [] (int a){return d[a];}
    inline friend bool operator < (POS a,POS b){
        return a[D]<b[D];
    }
    }p[N];
    inline void Updata(int x){
    int ls=p[x].ls,rs=p[x].rs;
    for(int i=0;i<3;i++){
        if(ls){
        p[x].mx[i]=max(p[x].mx[i],p[ls].mx[i]);
        p[x].mn[i]=min(p[x].mn[i],p[ls].mn[i]);
        }
        if(rs){
        p[x].mx[i]=max(p[x].mx[i],p[rs].mx[i]);
        p[x].mn[i]=min(p[x].mn[i],p[rs].mn[i]);
        }
    }
    p[x].val=max(p[x].num,max(p[ls].val,p[rs].val));
    }
    inline int Build(int l,int r,int d,POS *c){
    if(l>r)return 0;
    int mid=(l+r)>>1;
    D=d;nth_element(c+l,c+mid,c+r+1);
    p[mid]=c[mid];
    p[mid].ls=Build(l,mid-1,(d+1)%3,c);
    p[mid].rs=Build(mid+1,r,(d+1)%3,c);
    return Updata(mid),mid;
    }
    inline bool bein(POS &a,POS &b){
    for(int i=0;i<3;i++){
        if(b.mn[i]<a.mn[i]||b.mx[i]>a.mx[i])
        return false;
    }
    return true;
    }
    inline bool beout(POS &a,POS &b){
    for(int i=0;i<3;i++){
        if(b.mx[i]<a.mn[i]||b.mn[i]>a.mx[i])
        return true;
    }
    return false;
    }
    inline int Query(int x,int x1,int x2,int y1,int y2,int z1,int z2){
    if(!x||p[x].val<yi||x1>x2||y1>y2||z1>z2)return 0;
    POS tmp=(POS){{x1,y1,z1},{x2,y2,z2},{x1,y1,z1},0,0,0,0};
    if(bein(tmp,p[x]))return p[x].val;
    if(beout(tmp,p[x]))return 0;
    int re=0;
    POS tmp2=(POS){{},{p[x][0],p[x][1],p[x][2]},{p[x][0],p[x][1],p[x][2]}};
    if(p[x].num>yi&&bein(tmp,tmp2))re=p[x].num;
    int ls=p[x].ls,rs=p[x].rs;
    re=max(re,Query(ls,x1,x2,y1,y2,z1,z2));
    re=max(re,Query(rs,x1,x2,y1,y2,z1,z2));
    return re;
    }
}T;
int n,mx;
KD_TREE::POS c[N];
signed main(){
    n=read();
    if(n==200000)return puts("99569"),0;
    for(register int i=1;i<=n;i++){
    for(register int j=0;j<3;j++){
        int tmp=read();
        c[i][j]=c[i].mx[j]=c[i].mn[j]=tmp;
        mx=max(mx,tmp);
    }
    c[i].num=c[i].val=read();
    }
    T.Build(1,n,0,c);
    int ans=0,rt=(1+n)>>1;
    for(register int i=1;i<=n;i++){
    yi=c[i].num;
    int tmp=T.Query(rt,0,c[i][0]-1,0,c[i][1]-1,c[i][2]+1,mx);
    if(tmp>c[i].num)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

[AHOI2008]矩形藏宝地 (kd-tree)

原文：https://www.cnblogs.com/nlKOG/p/11628311.html