相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4456
神犇题解：http://blog.csdn.net/neither_nor/article/details/51733997
解题报告
将询问离线后考虑分治
不停地将区间尽量划分成正方形
考虑每一个块内的询问：
1. 最优路径经过中轴线
那么我们枚举中轴线上的每一个点
跑一遍到块内所有点的最短路
然后用这个东西来更新答案2. 最优路径不经过中轴线
那么我们递归处理
于是我们就在 $O(n\sqrt n {\log ^2}n)$ 的时间复杂度内解决这个问题了
然而复杂度可以被证明到少个 $log$ 参见：http://blog.csdn.net/neither_nor/article/details/51733997
As a Newbie, I am continuously exploring online for articles that can aid me. Thank you
Very nice post and straight to the point. I am not sure if this is actually the best place to ask but do you people have any thoughts on where to get some professional writers? Thank you 🙂