P5471

我只会签到题.jpg。 显然可以使用二维线段树优化建图拿到一定的部分分，但是这并不优秀。 考虑从值域上来入手 dijkstra。看做是装置间的最短路顺带更新节点，那么我们可以写一个树套树来维护这一些待更新的点，因为 dist 是递增的，所以可以更新后删去这些点，然后就可以 $n\log n$ 的空间 ......