Public Round 12

电塔

令操作结束后序列是 $y_1,y_2,\cdots,y_n$，容易发现，把 $x,y$ 分别排序，将 $x_1$ 变为 $y_1$，将 $x_2$ 变为 $y_2$ ……，是最优的。

于是问题变成了，把 $x_i$ 升序排列后，要求对于所有 $i(2 \le i \le n),x_i-x_{i-1} \ge d$，求最少操作次数。

考虑其差分序列，直接套用 UOJ-雪灾与外卖 的模拟费用流算法，能得 $70$ 分。

再次转化，将 $x_i$ 减去 $(i-1)d$，问题就变成了让 $x_i$ 不降，求最少操作次数，这个能直接做到 $O(n \log n)$。

并查集

先拆一下贡献，对于每条边，将它的经过次数加到答案里，最后答案加上 $2(n-1)$，就是真正的答案。

考虑把 $u$ 挂在 $v$ 上的过程，令 $S$ 表示 $u$ 所在连通块的点集，则 find(u) 到 find(v) 这条边的经过次数为：$-2(|S|-1)-1+\sum_{x \in S} deg(x)$。令这一坨式子为一个连通块的权值，显然，我们应该把 $u,v$ 所在连通块中，权值较大的挂在权值较小的上面。

继续观察，假设 $u$ 所在连通块的权值比 $v$ 大，那么把 $v$ 里面的点一个一个挂到 $u$ 上一定是更优的。

枚举起点，将树定根在起点，问题变成了，每个点有一个权值，将 $0,1, \cdots, n-1$ 放到每个点上，要求父亲的数大于儿子，最大化每个点上权值乘上数的和。这是经典的问题，每次取权值最大的，它上面的数一定是父亲的 $-1$，将它和父亲合并就行，新权值设为连通块内的平均数。

复杂度 $O(n^2 \log n)$。

划分序列

考虑最朴素的 dp：$dp(i)$ 表示前 $i$ 个数的最大价值，转移 $dp(i)+mex(i+1,j) \cdot sum(i+1,j) \rightarrow dp(j)(j-i \le k)$。

从 $1$ 到 $n$ 依次计算 dp 值，令当前算到的位置为 $i$，先维护每个位置到 $i$ 这一段的 $mex$，直接开珂朵莉树维护其连续段，能分析出总共只有 $O(n)$ 次连续段的变化。

转移考虑根号重构，令 $B=\lfloor\sqrt{n} \rfloor$，若 $i \bmod B=0$，则重构 $[i-k+B,i]$ 这一段的贡献，转移的时候对于散块暴力算，复杂度 $O(n \sqrt {n})$，实现起来很多细节。

据说存在 polylog 做法，敬请期待官方题解（。