luoguP3769 [CH弱省胡策R2]TATT

PS：做这题前先切掉 P4148简单题，对于本人这样的juruo更助于理解，当然dalao就当练练手吧

题目大意：现在有n个四维空间中的点，请求出一条最长的路径，满足任意一维坐标都是单调不降的

偏模板的K-D Tree

题目没规定起点，则从任意一点出发，按维度优先级以及每个维度坐标为关键字排序，

每点作为终点查询一次，再插入，其他就是模板化的代码了

这里用到了一个小技巧，就是初始化将子树0的值赋值，避免过多的特判，使代码更加简洁

for(LL i=0;i<=3;++i)

        tree[0].mi[i]=inf,tree[0].mx[i]=-inf; tree[0].maxn=-inf;

My complete code：

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

typedef long long LL;

const LL maxn=1e5+10;

const LL inf=1e9;

inline LL read(){

    LL x=0,f=1; char c=getchar();

    while(c<'0'||c>'9'){

        if(c=='-') f=-1; c=getchar();

    }

    while(c>='0'&&c<='9'){

        x=x*10+c-'0'; c=getchar();

    }

    return x*f;

}

struct node{

    LL son[2],d[4],maxn,size,val,mi[4],mx[4];

}tree[maxn],t2[maxn],tmp;

bool operator < (node g1,node g2){

    for(LL i=0;i<=3;++i){

        if(g1.d[i]<g2.d[i]) return 1;

        if(g1.d[i]>g2.d[i]) return 0;

    }return 0;

}

LL n,ans,ans_maxn,top,cnt,root,WD; LL sta[maxn];

inline void update(LL now){

    LL son0=tree[now].son[0],son1=tree[now].son[1];

    for(LL i=0;i<=3;++i){

        tree[now].mi[i]=min(min(tree[son0].mi[i],tree[son1].mi[i]),tree[now].d[i]);

        tree[now].mx[i]=max(max(tree[son0].mx[i],tree[son1].mx[i]),tree[now].d[i]);

    }

    tree[now].maxn=max(tree[now].val,max(tree[son0].maxn,tree[son1].maxn));

    tree[now].size=tree[son0].size+tree[son1].size+1;

}

inline bool cmp(LL g1,LL g2){

    return tree[g1].d[WD]<tree[g2].d[WD];

}

LL build(LL l,LL r,LL wd){

    if(l>r)

        return 0;

    LL mid=(l+r)>>1;

    WD=wd;

    nth_element(sta+l,sta+mid,sta+r+1,cmp);

    LL now=sta[mid];

    tree[now].son[0]=build(l,mid-1,(wd+1)%4);

    tree[now].son[1]=build(mid+1,r,(wd+1)%4);

    update(now);

    return now;

}

void pai(LL now){

    if(!now)

        return;

    sta[++top]=now;

    LL son0=tree[now].son[0],son1=tree[now].son[1];

    pai(son0); pai(son1);

}

inline void check(LL &now,LL wd){

    LL son0=tree[now].son[0],son1=tree[now].son[1];

    if(tree[now].size*0.75<tree[son0].size||tree[now].size*0.75<tree[son1].size){

        top=0;

        pai(now);

        now=build(1,tree[now].size,wd);

    }

}

void insert(LL &now,LL wd){

    if(!now){

        now=++cnt;

        tree[now]=tmp;

        for(LL i=0;i<=3;++i)

            tree[now].mi[i]=tree[now].mx[i]=tree[now].d[i];

        tree[now].maxn=tree[now].val; tree[now].size=1;

        return;

    }

    if(tmp.d[wd]<tree[now].d[wd])

        insert(tree[now].son[0],(wd+1)%4);

    else

        insert(tree[now].son[1],(wd+1)%4);

    update(now);

    check(now,wd);

}

inline LL dis(node g1,node g2){

    for(LL i=0;i<=3;++i)

        if(g1.d[i]>g2.d[i])

            return 0;

    return g1.val;

}

inline LL into(LL now){

    if(!now)

        return 0;

    LL sum=0;

    for(LL i=0;i<=3;++i)

        if(tree[now].mx[i]<=tmp.d[i])

            ++sum;

    if(sum==4)

        return 4;

    for(LL i=0;i<=3;++i)

        if(tree[now].mi[i]>tmp.d[i])

            return 0;

    return 1;

}

void query(LL now){

    ans=max(dis(tree[now],tmp),ans);

    LL son0=tree[now].son[0],son1=tree[now].son[1];

    LL dl=into(son0),dr=into(son1);

    if(dl==4)

        ans=max(tree[son0].maxn,ans);

    else if(dl&&ans<tree[son0].maxn)

        query(son0);

    if(dr==4)

        ans=max(tree[son1].maxn,ans);

    else if(dr&&ans<tree[son1].maxn)

        query(son1);

}

int main(){

    n=read();

    for(LL i=1;i<=n;++i){

        for(LL j=0;j<=3;++j)

            t2[i].d[j]=read();

        t2[i].val=1;

    }

    sort(t2+1,t2+n+1);

    for(LL i=0;i<=3;++i)

        tree[0].mi[i]=inf,tree[0].mx[i]=-inf; tree[0].maxn=-inf;

    for(LL i=1;i<=n;++i){

        ans=0;

        tmp=t2[i];

        query(root);

        tmp.val+=ans;

        ans_maxn=max(tmp.val,ans_maxn);

        insert(root,0);

    }

    printf("%lld",ans_maxn);

    return 0;

}