原题：P2479 [SDOI2010]捉迷藏。

他想找一个地点，使得该地点到（除了这个地点以外的）最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。

这个问题可以使用 $k=2$ 情况的 KDT 解决。

下面有两篇题解，在建树的时候都没有使用方差等手段判断目前按照哪一维分割最优。

• Solution.1 这一篇是直接同时对所有点建树，每一次选择上上次不同的维度分割。这样不开 O2 是过不去的，只有 50pts。
• Solution.2 这一篇是每次只插入一个点然后使用替罪羊树的方式判断并重构树，不开 O2 可过。但是每次建立/重构子树的时候并没有判断哪个分割维度更优，都是直接选择维度进行分割。

两篇都没有判断并选择更优的那个维度进行分割，但是最后的结果却不同，想问第二种方式的优势在哪里，两种方式的时间复杂度的区别。

另：想问一下在 Solution.1 中，查询时的 KDT 邻域查询单次时间复杂度最坏是否是 $O(n)$ 的；如果是，同为邻域查询的 Solution.2 为什么可过，是数据的问题还是实现方面的问题。

orz。