为啥 KD−Tree 套 Trie 能跑过 log2 呀
一开始写树套树不开 O2 过不了,剪枝了一下就直接最优解??
能不能调整点的离散程度来卡满 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的部分大概如上……