UOJ Logo zgjkt的博客

博客

各种K-D Tree

2016-05-25 13:54:15 By zgjkt

【bzoj2648】$SJY$摆棋子

题目大意

在一个很大的棋盘上,摆好了$n$个黑色棋子,现在执行$m$次操作,分为两种:

  1. 摆一个黑色棋子

  2. 摆一个白色棋子,同时输出距离这个棋子最近的一个黑色棋子与它的距离(曼哈顿距离)

值得注意的是,一个地方可以放两个棋子

数据范围

$n,m\leqslant 500000$


题解

对于这一个问题,有一个简单思路,每次新摆一个白色棋子然后枚举黑色棋子,计算曼哈顿距离

很好,但是$n$,$m$到了五十万[捂脸]

炸弹熊

这时候我们引入一个东西,叫做$K-D\ Tree$

Tree?这是二维的图哦

嗯,实际上这是引入$K-D\ Tree$,而不是别的什么玄学结构的原因之一

这个$Tree$是这样建树的:

  1. 选定一个维度

  2. 针对每个点在这个维度上的参数$a_1,a_2,a_3..a_n$,用$STL$中的$nth\_element()$排序,使得在中间值左边的值全都比它小,右边的值全都比它大,但不保证有序

  3. 把中间值取出,把这个点当成根节点

  4. 选定另一个维度,递归左边的值(左平面)作为左子树,再递归右边的值(右平面)作为右子树

  5. 递归完之后更新根节点记录的信息

当然如果只有一个维度,它的效率比别的数据结构较之一般,但是在多维度上,就显示出很强势的一面啦

坏笑熊

对于这道题,插入和查询怎么办?

插入一个新的节点,只要针对某一维度上的参数与节点作比较,然后递归到子树即可

查询就需要节点记录的信息了

例如这道题,节点记录平面上极值点的坐标参数,然后比较对于查询位置来说哪个平面上的极值点更近,就递归哪个平面(子树)

关于其他的东西,我在代码旁做了比较详细的注释,那么这道题的题解就结束了!

鼓掌熊


代码

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7ffffff
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,root,D;
struct data{
    int c[2],mn[2],mx[2],l,r;
    data(int x=0,int y=0){l=r=0,c[0]=x,c[1]=y;}
}p[500500];

bool operator<(data a,data b){return a.c[D]<b.c[D];} 
inline int dis(data a,data b){return abs(a.c[0]-b.c[0])+abs(a.c[1]-b.c[1]);}

struct kdtree{
    int ans;
    data t[1000500],T;
    void pushup(int k){        //更新平面内两个维度的参数极大极小值 
        data l=t[t[k].l],r=t[t[k].r];         
        For(i,0,1){
            if (t[k].l) t[k].mn[i]=min(t[k].mn[i],l.mn[i]),t[k].mx[i]=max(t[k].mx[i],l.mx[i]);
            if (t[k].r) t[k].mn[i]=min(t[k].mn[i],r.mn[i]),t[k].mx[i]=max(t[k].mx[i],r.mx[i]);
        }
    }
    int build(int l,int r,int dim){     //dim是每次建树的维度 
        D=dim;       //确认排序时的关键值(当前维度上的参数) 
        int mid=(l+r)>>1;
        nth_element(p+l,p+mid,p+r+1);        //比较参数,排序使得中间值左边的参数比它小,右边的参数比它大(不保证左右有序) 
        t[mid]=p[mid];
        For(i,0,1) t[mid].mn[i]=t[mid].mx[i]=t[mid].c[i];
        if (l<mid) t[mid].l=build(l,mid-1,dim^1);        //分成两个平面,更换维度递归(图是二维) 
        if (r>mid) t[mid].r=build(mid+1,r,dim^1);
        pushup(mid);    //回溯更新 
        return mid;
    }


    void insert(data p){
        T=p;
        insert(root,0);
    }
    void insert(int k,int dim){
        if (T.c[dim]>=t[k].c[dim]){      //比较当前维度上根节点的参数与新节点的参数 
            if (t[k].r) insert(t[k].r,dim^1);       //递归右子树 
            else{
                t[k].r=++n,t[n]=T;        //插入新节点 
                For(i,0,1) t[n].mn[i]=t[n].mx[i]=t[n].c[i];
            }
        }
        else{
            if (t[k].l) insert(t[k].l,dim^1);       //递归左子树 
            else{
                t[k].l=++n,t[n]=T;        //插入新节点 
                For(i,0,1) t[n].mn[i]=t[n].mx[i]=t[n].c[i];
            }
        }
        pushup(k);      //回溯更新 
    }


    int get(data p){
        int sum=0;
        For(i,0,1) sum+=max(p.mn[i]-T.c[i],0)+max(T.c[i]-p.mx[i],0);
        return sum;
    }
    int query(data p){
        ans=inf,T=p;
        query(root);
        return ans;
    }
    void query(int k){
        int d,dl=inf,dr=inf;
        d=dis(t[k],T);        //中间值到询问位置的距离 
        ans=min(ans,d);
        if (t[k].l) dl=get(t[t[k].l]);        //记录询问位置离左平面上的点的最短距离    
        if (t[k].r) dr=get(t[t[k].r]);        //记录询问位置离右平面上的点的最短距离  
        if (dl<dr){
            if (dl<ans) query(t[k].l);
            if (dr<ans) query(t[k].r);
        }
        //如果dl<dr,可能先递归左平面更新后得到ans<dr,也就是已经确定更优,那么不需要再递归右平面,以下同理
        else{
            if (dr<ans) query(t[k].r);
            if (dl<ans) query(t[k].l);
        }
    }
}kd;

int main(){
    n=read(),m=read();
    For(i,1,n) p[i].c[0]=read(),p[i].c[1]=read();
    root=kd.build(1,n,0);
    while (m--){
        int flag=read(),x=read(),y=read();
        if (flag==1) kd.insert(data(x,y));
        else printf("%d\n",kd.query(data(x,y)));
    }
    return 0;
}

安利一下:

K-D Tree的简介和表示

K-D Tree 数据结构


【bzoj1941】$Hide\ and\ Seek$

题目大意

给定$n$个点的坐标$(x,y)$,在其中选定一个点$A$

使得$A$到最远点的距离减去到最近点的距离最小,然后输出这个最小值

注意两点,此题的距离指的是曼哈顿距离

且$A$到最近点的距离不能为零,即最近点不能是其本身

数据范围

$n\leqslant 500000,0\leqslant x,y\leqslant 10^8$,保证数据没有重点保证$n\leqslant 2$


题解

在上一题,在询问中我们需要求到最近点的距离

这一题其实也差不多,只是要在询问中再求到最远点的距离,具体看代码

由于数据范围又是在五十万之内,是不是很熟悉?

所以我是暴力枚举每个点,如果有更优值就更新答案

捂脸熊

或许有更好的玄学(划掉)想法呢?

思考熊


程序

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7ffffff
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,root,ans,D;
int x[500500],y[500500];
struct data{
    int c[2],mn[2],mx[2],l,r;
    data(int x=0,int y=0){l=r=0,c[0]=x,c[1]=y;}
}p[500500];

bool operator<(data a,data b){return a.c[D]<b.c[D];}
inline int dis(data a,data b){return abs(a.c[0]-b.c[0])+abs(a.c[1]-b.c[1]);}

struct kdtree{
    int mx,mn;
    data t[1000500],T;
    void pushup(int k){
        data l=t[t[k].l],r=t[t[k].r];
        For(i,0,1){
            if (t[k].l) t[k].mn[i]=min(t[k].mn[i],l.mn[i]),t[k].mx[i]=max(t[k].mx[i],l.mx[i]);
            if (t[k].r) t[k].mn[i]=min(t[k].mn[i],r.mn[i]),t[k].mx[i]=max(t[k].mx[i],r.mx[i]);
        }
    }
    int build(int l,int r,int dim){
        D=dim;
        int mid=(l+r)>>1;
        nth_element(p+l,p+mid,p+r+1);
        t[mid]=p[mid];
        For(i,0,1) t[mid].mn[i]=t[mid].mx[i]=t[mid].c[i];
        if (l<mid) t[mid].l=build(l,mid-1,dim^1);
        if (r>mid) t[mid].r=build(mid+1,r,dim^1);
        pushup(mid);
        return mid;
    }


    int query(data p){
        T=p;
        mx=-inf;querymx(root);
        mn=inf;querymn(root);
        return mx-mn;
    }
    int getmn(data p){
        int sum=0;
        For(i,0,1) sum+=max(T.c[i]-p.mx[i],0)+max(p.mn[i]-T.c[i],0);
        return sum;
    }
    int getmx(data p){
        int sum=0;
        For(i,0,1) sum+=max(abs(T.c[i]-p.mx[i]),abs(p.mn[i]-T.c[i]));
        return sum;
    }
    void querymn(int k){
        int d=dis(t[k],T),dl=inf,dr=inf;
        if (d) mn=min(mn,d);
        if (t[k].l) dl=getmn(t[t[k].l]);
        if (t[k].r) dr=getmn(t[t[k].r]);
        if (dl<dr){
            if (dl<mn) querymn(t[k].l);
            if (dr<mn) querymn(t[k].r);
        }
        else{
            if (dr<mn) querymn(t[k].r);
            if (dl<mn) querymn(t[k].l);
        }
    }
    void querymx(int k){
        int dl=-inf,dr=-inf;
        mx=max(mx,dis(t[k],T));
        if (t[k].l) dl=getmx(t[t[k].l]);
        if (t[k].r) dr=getmx(t[t[k].r]);
        if (dl>dr){
            if (dl>mx) querymx(t[k].l);
            if (dr>mx) querymx(t[k].r);
        }
        else{
            if (dr>mx) querymx(t[k].r);
            if (dl>mx) querymx(t[k].l);
        }
    }
}kd;

int main(){
    n=read();
    For(i,1,n){
        x[i]=read(),y[i]=read();
        p[i].c[0]=x[i],p[i].c[1]=y[i];
    }
    root=kd.build(1,n,0);
    ans=inf;
    For(i,1,n) ans=min(ans,kd.query(data(x[i],y[i])));
    printf("%d\n",ans);
    return 0;
}


完结撒花!!!

评论

absi2011
不是太明白到底怎么做的求解释的再详细点..
Recursion
2648正解到底是啥啊...
WrongAnswer
复杂度?
qmqmqm
名字叫“各种K-D Tree”但只有一个题目是怎么回事。。
Sengxian
https://blog.sengxian.com/algorithms/k-dimensional-tree

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。