听取MLE声一片 @ 2025-09-20 19:01:44
网络赛C题，这份代码为什么会TLE？
https://www.luogu.com.cn/paste/r57pjpez
何意味。
by simple_child @ 2025-09-20 19:06:06
%%%
by Velleity @ 2025-09-20 19:32:36
《萌新金钩大佬》orz
by _•́へ•́╬_ @ 2025-09-20 20:48:53
我2log都日过去了
by ShwStone @ 2025-09-23 10:18:26
我觉得是 multiset 操作过多了
真有必要写这么复杂吗
by ShwStone @ 2025-09-23 10:20:08
另外注意一下是不是维护过多了：
如果某个 T 点，是多个 S 点的最近点，那怎么办？要把所有 S 都 lowerbound 更新吗？复杂度不就炸了吗？这里有一个观察：对于两个 S 点 u,v，如果他们的最近点都是 w，而且 u 离 w 更近，那么 v 永远不可能对最近点有贡献，因为能和 v 连的 T 一定能和 u 连，而且更近。所以不更新 v 就行了。这样每次弹出堆顶只要更新一个点。时间复杂度 n log n。
https://www.zhihu.com/question/1951563453396390554/answer/1953027181774090700