ppip @ 2022-10-14 20:25:49
发现莫队双指针的转移用“平面曼哈顿距离最小生成树”优化应当最优，如何证明或证伪这东西优化莫队复杂度也在
by dehsirehC @ 2022-10-14 20:36:32
x,y 坐标分别分成根号份，这样会形成 n 份，每份左下角一个询问，是不是就是根号级别的？
瞎胡成弱智了轻喷
by CreutzWilknare @ 2022-10-14 21:16:06
莫队转化成于平面曼哈顿旅行商问题，最小生成树做旅行商在算法导论里是专门提到的一个常数级别近似算法。
因为只在最小生成树上走，所以答案必定不会超过最优解（也就是只移动指针的莫队理论的移动次数）的两倍
然后就证完了。
by ppip @ 2022-10-14 21:58:28
@Karasu 我想问的就是，只移动指针的莫队理论的移动次数为啥是
by CreutzWilknare @ 2022-10-14 22:54:27
@ppip 同时证明上下界都是 n sqrt(n) 不就行了……
by Cat_shao @ 2022-10-15 12:11:36
@ppip 这问题我问过，见 https://www.luogu.com.cn/discuss/497758
by Cat_shao @ 2022-10-15 12:13:07
大概意思是曼哈顿最小生成树是 N sqrt n 的，曼哈顿 TSP 不会超过这个生成树的二倍