BZOJ2716/Violet 3/天使玩偶

Posted on By 二价氢

#题目描述

给一个点,在线询问最近点

#做法

K-d Tree (K维树)

如下图为平面上的若干点:

我们按照一定的方式将这个平面划分

同时可以建立像下面这个类似于线段树的东西:

根据每个点X,Y的关系,交替建立如上的树状结构

插入类似于线段树的插入,查询的时候同插入的时候类似,找到欲查询的点所在的区块,一个重要的结论就是,和这个点距离最近的点一定在这个点所在的区块内

每次查询的时候在每个区块内找一下就够了,时间复杂度为

#复杂度分析

时间复杂度为,其中M代表操作次数,N代表所有点数

#AC Code

AC Code