题解：夏终
喵仔牛奶
·
·
题解
Solution
在 Kruskal 的过程中，每个连通块维护一条链，最初链是孤点，合并两集合则将两集合的链首尾相接。
结论 1：在原图上加入若干边后的 MST 的边权和等于重构后的链上加入相同边后的 MST 的边权和。
:::info[证明]
这样重构后，对于任意 w，保留边权 \le w 的边的连通性不会变。因此加入若干边后的 MST 边权和相同。
:::
因此原问题转化为 A 性质。
考虑最优解选择的 E 中的边为集合 P，那么这些边将图连成一个联通块，选择 x\in\argmin\{b_i\}，E' 中边的最优选择方法显然为不包含 x 的联通块的选择一个点和 x 连边。
令 C'=b_x+C，相当于除了连的边外，一个联通块 S 还需要额外付出 \min_{i\in S}\{b_i\}+C' 的代价（最后答案需要减去 b_x+C'）。
考虑 DP，记 w_i 为连接 i-1 和 i 的边的边权，设 f_{i,j,0/1} 为考虑 [1,i]，有 j 个联通块，最后一个联通块 仍未计算/已经计算 额外代价的最小代价和。转移：
f_{i,j,0}=\min(f_{i-1,j-1,1},f_{i-1,j,0}+w_i)
f_{i,j,1}=\min(f_{i-1,j,1}+w_i,f_{i-1,j-1,1}+b_,f_{i-1,j,0}+w_i+b_i)
答案即为 \min\{f_{n,i,1}+i\times C'\}.
结论 2：f_{n,i,0/1} 关于 i 有凸性。
:::info[证明]
只证明 f_{n,i,1} 关于 i 有凸性，最后一维是 0 证明差不多。
考虑如下的一个费用流模型：
- 对于 i\in[1,n]，i\to n+i，流量为 1，费用为 0；
- 对于 i\in[1,n]，n+i\to i-1，流量为 1，费用为 0；
- 对于 i\in[1,n]，n+i\to T，流量为 1，费用为 b_i；
- 对于 i\in[1,n]，S\to i，流量为 1，费用为 -w_{i+1}（w_{n+1}=-\infty）；
可以发现增广 x 次的费用加上 \sum w_i 即为 f_{n,x,1}，根据费用流的凸性，结论成立。
:::
重定义多项式加法乘法为每位取 \min 和 (\min,+) 卷积，那么 f_{i,0/1} 可以看作一个多项式。此时 DP 的转移可以写成矩阵乘法的形式，使用闵可夫斯基和可以在 \mathcal O(A+B) 时间内合并长度为 A,B 的区间的答案。
对于多项式 A，定义 f(A)=\min\{A_i+i\times C'\}。可以发现对于多项式 A,B，f(AB)=f(A)+f(B),f(A+B)=\min(f(A),f(B))。
现在的问题是每个点有一个次数不超过 1 的多项式组成的矩阵，每次单点修改，然后对这些矩阵的乘积的某一项 A 求 f(A)。
将序列按 B 的长度分块，每个块内部维护一棵线段树，线段树的节点维护区间内多项式矩阵的乘积。对于修改和查询：
- 单点修改块内的 b_i 直接在线段树上修改，修改一次的复杂度为 \sum\frac{B}{2^i}=\mathcal O(B)。
- 查询时二分凸壳求出每个块的转移矩阵的 f(*) 值，每个块矩阵相乘即为答案。
取 B=\sqrt{n\log n}，复杂度为 \mathcal O(n\log n+q\sqrt{n\log n})。可以通过。
更进一步，离线逐块处理，堆积询问，修改时将累积的询问基数排序然后一次性求解。设累积了 Q 个询问，则复杂度为 \mathcal O(\text{sort}(Q)+B)。将基数排序视作线性，那么取 B=\sqrt{n} 就得到了 \mathcal O(n\log n+q\sqrt n) 的复杂度。
轻度卡常。