Luogu分析首先容易看出一个暴力，即每个点向能到达的点连边，然后最短路即可。然而边数是 $\mathcal{O}(n^2)$ 级别的，我们需要优化连边。由于是向矩形范围内的点连边，所以考虑 KD-Tree 优化连边。对于城市 $u$ 向矩形连的边，我们在 KD-Tree 上遍历：如果当前节点范围包含在矩形内，则 $u$ 直接向这个节点连边；如果当前节点范围与矩形无交，则直接返回；否则，如果...
LuoguLOJ分析暴力就是把所有圆排序后直接 $\mathcal{O}(n^2)$ 模拟。考虑用 KD-Tree 优化模拟过程。我们把每个圆看作它的外接矩形，然后对于当前删去的圆在 KD-Tree 上递归，如果圆与矩形没有交则不会更新，可以直接返回。然后建树时按方差选维度就可以过了。代码// =================================== // author: ...
LuoguLOJ分析暴力就是维护一个大小为 $k$ 的小根堆，然后 $\mathcal{O}(n^2)$ 枚举。考虑用 KD-Tree 优化。对于每个点在 KD-Tree 上递归，如果当当前矩形的最大距离比堆顶小则不可能更新答案，可以直接返回。因为是每对点算了两遍所以堆的大小应为 $2k$，为了方便可以先插 $2k$ 个 $0$ 进去。代码// =======================...
Luogu分析还是 KD-Tree 板子。插入时利用替罪羊树重构那一套保证平衡。查询时判断查询矩形和当前矩形是否有交，如果完全包含直接返回当前矩形和，部分包含就递归下去，否则返回 $0$。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ===...
Luogu分析KD-Tree 板子。插入时可能会让 KDT 不平衡，用类似于替罪羊树的方式定期重构即可。查询时利用到矩形的最短距离剪枝。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =============================...