论根号log如何跑过俩log

回复帖子

@yspm  2021-06-11 12:17 回复

为啥 $\rm{KD-Tree}$ 套 $Trie$ 能跑过 $\log^2$ 呀

一开始写树套树不开 $O2$ 过不了,剪枝了一下就直接最优解??

能不能调整点的离散程度来卡满 $\rm{KD-Tree}$ 呀

求教

    inline void insert(int &p,int dep){
        int x=p; if(p<=Pre) p=++num,ls[p]=ls[x],rs[p]=rs[x]; if(dep==-1) return ; 
        if(V>>dep&1) insert(rs[p],dep-1); else insert(ls[p],dep-1); 
        return ;
    }
    int Ans,x1,y1,x2,y2,nd[N],qu;
    inline int query(int x,int dep){
        if(!x) return 0; if(dep==-1) return 0;
        if(V>>dep&1){
            if(ls[x]) return query(ls[x],dep-1)+(1<<dep);
            return query(rs[x],dep-1);
        }else{
            if(rs[x]) return query(rs[x],dep-1)+(1<<dep);
            return query(ls[x],dep-1);
        }
    }
    inline void Query(int p){
        if(x1<=mn[p][0]&&x2>=mx[p][0]&&y1<=mn[p][1]&&y2>=mx[p][1]) return ckmax(Ans,query(rt[p],Pos));
        if(x2<mn[p][0]||x1>mx[p][0]||mn[p][1]>y2||mx[p][1]<y1) return ;
        if(query(rt[p],Pos)<=Ans) return ;
        if(pos[p][0]>=x1&&pos[p][0]<=x2&&pos[p][1]>=y1&&pos[p][1]<=y2) Ans=max(Ans,V^val[p]);
        if(Ls[p]) Query(Ls[p]); if(Rs[p]) Query(Rs[p]); 
        return ;
    }
    inline void push_up(int x){
        for(reg int i=0;i<=1;++i){
            mx[x][i]=mn[x][i]=pos[x][i];
            if(Ls[x]) ckmax(mx[x][i],mx[Ls[x]][i]),ckmin(mn[x][i],mn[Ls[x]][i]);
            if(Rs[x]) ckmax(mx[x][i],mx[Rs[x]][i]),ckmin(mn[x][i],mn[Rs[x]][i]);
        }Pre=num; rt[x]=Merge(rt[Ls[x]],rt[Rs[x]],Pos); V=val[x]; insert(rt[x],Pos);  
        return ;
    }
    inline int build(int l,int r,int d){
        if(r<l) return 0; Dim=d; int mid=(l+r)>>1,x=++tot; nth_element(p+l,p+mid,p+r+1);
        pos[x][0]=p[mid].p[0]; pos[x][1]=p[mid].p[1]; val[x]=p[mid].val;
        if(l<mid) Ls[x]=build(l,mid-1,d^1); if(r>mid) Rs[x]=build(mid+1,r,d^1);
        return push_up(x),x;
    }

kdt的部分大概如上……

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。