CF1580E Railway Construction

铁路系统中有 (n) 个车站和 (m) 条双向边，有边权，无重边。这些双向边使得任意两个车站互相可达。

你现在要加一些单向边 ((u,v,w)) ，(w) 随便定，代价是 (a_u) ，使得从 (1) 号车站出发到每个车站都有至少两条边不相交的路线，并且最短路不改变。

由于不可控因素，(a) 序列会受到 (q) 次修改，每次让 (a_u leftarrow a_u+x) ，并求当前的最小代价。

(1le n,m,q le 3cdot 10^5,1le a_ile 10^9, 1le xle 4cdot 10^8) 。

Solution

首先从 (1) 出发跑最短路，显然非最短路边是无用的。因此建出最短路图，我们在 DAG 上讨论问题。

可以发现，将所有点按照 ( ext{dis}) 排序是合法的拓扑序，而只要有一个点入度 (ge 2) ，那么它已经满足要求了。

所以，问题转化为将所有入度 (=1) 的点新连一条边，那么肯定挑拓扑序在它之前的 (a) 最小的点。

因此在拓扑序上维护前缀 (a) 最小值和次小值的点即可，暴力复杂度 (mathcal O(nq)) 。

考虑优化，我们将所有改变前缀最小/次小的位置丢进一个 set 里，显然二元组 (最小值，次小值) 构成一个个区间。倒着处理询问（即每次 (a_u) 变小）：

(u) 是这个区间的最小值

可以发现它对区间不会造成任何影响，只对答案产生了影响；求对答案影响的部分，可以用一棵线段树去维护；
(u) 是这个区间的次小值

注意到不同区间的次小值一定不一样（这个显然），因此只有撑死 (1) 个区间符合该条件，暴力修改即可；
(u) 既不是这个区间的最小值，也不是次小值

类比颜色段均摊的思想，它修改的区间端点会从 set 里 erase 掉，同时把它加进 set 里，而 set 里的端点个数总计是 (mathcal O(n+q)) 的，因此直接暴力做即可。

总时间复杂度 (mathcal O(mlog m+(n+q)log n)) 。