CSP-SJX2019 解题报告

这种套路的东西，显然要枚举右端点。

假设某一段 \(a\) 的和为 \(x\)，\(b\) 的和为 \(y\)，新加入 \(i\) 位置，那么新产生的贡献为

\[\left(x+a_i\right)\left(y+b_i\right)-xy=xb_i+ya_i+a_ib_i
\]

记一下以 \(i\) 位置结尾的段的和即可，具体地，\(a_i\) 和 \(b_i\) 的贡献次数均为 \(i\) 次，所以处理完后分别加上 \(a_i\times i\) 和 \(b_i\times i\)。

我寻思着这只是加速克鲁斯卡尔算法，也不用剖析什么本质吧……

因为每行每列的边权分别相同，所以每次肯定连完以行或一列的边。

先把最小的行和列连了，假设连了 \(i\) 行和 \(j\) 列，新连一行会有 \(j-1\) 个点连过边了，只需要连 \(m-j\) 条新的边；新连一列会有 \(i-1\) 个点连过边了，只需要连 \(n-i\) 条新的边。

黑色代表未处理过的行列，空白代表不需要连的边，红色代表在列上连的边，绿色代表在行上连的边，蓝色代表新连的边。

为什么是正确的呢？因为本题的性质保证了只会有一个大连通块和没连过边的点。

巴特西