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

· · 题解

KD-Tree是一个好东西啊......KD-Tree是一种将K维空间里的点规整好的树结构,其实也不复杂,就是第一层按照第一维坐标分成左右两边,第二层再按照第二维坐标,第三再按第三维......当然,本题只有两个维度,这样的KD-Tree又称为2D-Tree

这样在查询的时候,我们知道,由于我们按当前维度的大小将左右子树分开了,所以我们通过提取两棵子树里的点x坐标最大/最小值,y坐标最大/最小值,可以看作这些点处于两个不相交的矩形里.我们可以算出当前要查询的点到矩形的最短曼哈顿距离,与当前获得的答案比较,决定是否查找那棵子树,达到剪枝的目的.复杂度和带剪枝的搜索一样,是O(玄学)

而插入就按照每个维度往左右子树插就行......可是令人绝望的是,这样子插了若干次之后,可能原树就被退化成一个近似于链的东西了.这个时候,我们就要利用替罪羊树的思想,设一个\alpha=0.75,如果对于点x,x的左右子树中的任意一棵的大小大于了x子树大小乘以\alpha,说明原树已经非常不平衡了,需要将其还原成一个点的序列(这一过程被称为拍扁),然后重建一次.当然,你也可以根据你的心情对\alpha值做调整.

最后放出代码:

#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;
}