题目传送门 闲的没事水一发博客 KDTree模板题，只不过维度增加，还是可以矩形分隔建树。查询还是按范围剪枝，最近的 M M M个点可以优先队列维护，如果发现队头不优了就弹，能加就加，维护一下就好了。 但是初始化有点问题，如果把原来的树覆盖掉，就会在一组神奇的数据死循环而得不出最优解，这样要么做完后递归删树，要么花内存再建出新的一棵树。~~不过写的没什么不对的啊I’m 不爽…~~不过内存够用，开大点也没事了… UPD：我太菜了，应该递归时把原左右儿子先删掉再建树…内存完美，时间完美… 时间 O ( n log 2 n ) O(n\log_2 n) O(nlog2n)- O ( n n ) O(n\sqrt n) O(nn ) Code
