题解 P4169 【[Violet]天使玩偶】

KD-Tree是一个好东西啊......KD-Tree是一种将K维空间里的点规整好的树结构,其实也不复杂,就是第一层按照第一维坐标分成左右两边,第二层再按照第二维坐标,第三再按第三维......当然,本题只有两个维度,这样的KD-Tree又称为2D-Tree 这样在查询的时候,我们知道,由于我们按当前维度的大小将左右子树分开了,所以我们通过提取两棵子树里的点x坐标最大/最小值,y坐标最大/最小值,可以看作这些点处于两个不相交的矩形里.我们可以算出当前要查询的点到矩形的最短曼哈顿距离,与当前获得的答案比较,决定是否查找那棵子树,达到剪枝的目的.复杂度和带剪枝的搜索一样,是O(玄学) 而插入就按照每个维度往左右子树插就行......可是令人绝望的是,这样子插了若干次之后,可能原树就被退化成一个近似于链的东西了.这个时候,我们就要利用**替罪羊树**的思想,设一个$\alpha=0.75$,如果对于点$x$,$x$的左右子树中的任意一棵的大小大于了$x$子树大小乘以$\alpha$,说明原树已经非常不平衡了,需要将其还原成一个点的序列(这一过程被称为**拍扁**),然后重建一次.当然,你也可以根据你的心情对$\alpha$值做调整. 最后放出代码: ```cpp #include<bits/stdc++.h> using namespace std; int read() { int q=0,w=1;char ch=' '; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar(); return q*w; } #define alph (0.75) const int N=1000005; struct point{int x[2];}p[N]; struct node{int mi[2],mx[2],ls,rs,sz;point tp;}tr[N]; int n,m,rt,cur,top,WD,ans,rub[N]; int operator < (point a,point b) {return a.x[WD]<b.x[WD];} int newnode() {//建立新节点 if(top) return rub[top--]; else return ++cur; } void up(int k) { int l=tr[k].ls,r=tr[k].rs; for(int i=0;i<=1;++i) { tr[k].mi[i]=tr[k].mx[i]=tr[k].tp.x[i]; if(l) tr[k].mi[i]=min(tr[k].mi[i],tr[l].mi[i]),tr[k].mx[i]=max(tr[k].mx[i],tr[l].mx[i]); if(r) tr[k].mi[i]=min(tr[k].mi[i],tr[r].mi[i]),tr[k].mx[i]=max(tr[k].mx[i],tr[r].mx[i]); } tr[k].sz=tr[l].sz+tr[r].sz+1; } int build(int l,int r,int wd) { if(l>r) return 0; int k=newnode(),mid=(l+r)>>1; WD=wd,nth_element(p+l,p+mid,p+r+1),tr[k].tp=p[mid]; //nth_element:使得序列某一位置x(此处是p+mid)是该序列的第x大数 tr[k].ls=build(l,mid-1,wd^1),tr[k].rs=build(mid+1,r,wd^1); up(k);return k; } void pia(int k,int num) {//拍扁 if(tr[k].ls) pia(tr[k].ls,num); p[num+tr[tr[k].ls].sz+1]=tr[k].tp,rub[++top]=k; if(tr[k].rs) pia(tr[k].rs,num+tr[tr[k].ls].sz+1); } void check(int &k,int wd) {//检查子树是否不平衡 if(alph*tr[k].sz<tr[tr[k].ls].sz||alph*tr[k].sz<tr[tr[k].rs].sz) pia(k,0),k=build(1,tr[k].sz,wd); } void ins(point tmp,int &k,int wd) {//插入 if(!k) {k=newnode(),tr[k].tp=tmp,tr[k].ls=tr[k].rs=0,up(k);return;} if(tr[k].tp.x[wd]<tmp.x[wd]) ins(tmp,tr[k].rs,wd^1); else ins(tmp,tr[k].ls,wd^1); up(k),check(k,wd);//记得在check之前要先pushup } int getdis(point tmp,int k) {//获得当前点到矩形的曼哈顿距离 int re=0; for(int i=0;i<=1;++i) re+=max(0,tmp.x[i]-tr[k].mx[i])+max(0,tr[k].mi[i]-tmp.x[i]); return re; } int dist(point a,point b) {return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);} void query(point tmp,int k) {//查询 ans=min(ans,dist(tmp,tr[k].tp)); int dl=INT_MAX,dr=INT_MAX; if(tr[k].ls) dl=getdis(tmp,tr[k].ls); if(tr[k].rs) dr=getdis(tmp,tr[k].rs); if(dl<dr) { if(dl<ans) query(tmp,tr[k].ls); if(dr<ans) query(tmp,tr[k].rs); } else { if(dr<ans) query(tmp,tr[k].rs); if(dl<ans) query(tmp,tr[k].ls); } } int main() { int bj; n=read(),m=read(); for(int i=1;i<=n;++i) p[i].x[0]=read(),p[i].x[1]=read(); rt=build(1,n,0); while(m--) { point tmp; bj=read(),tmp.x[0]=read(),tmp.x[1]=read(); if(bj==1) ins(tmp,rt,0); else ans=INT_MAX,query(tmp,rt),printf("%d\n",ans); } return 0; } ```