题解：P5012 水の数列

· · 题解

P5012 水の数列

然而这么出还是太简单了

upd 2025/2/3 23:04：这题坑太多了，以后再也不乱填非常简单了咕咕咕qwq。

一道很好的数据结构题。

给定长度为 N 的序列，记 d(x) 为对于所有的 v，使得这些序列中小于等于 v 的数恰好被划分为 x 个序列时，这些序列的长度的平方和除以 v 所得的数的最大值。

------------ 我们将题意整理成现在这样，意在展示**只要求出每一个** $d(k),k=1,2,...,k_m$，原题就可以通过**维护一个ST表**来解决。 观察题目，注意到能取到最大值的 $v$ 一定为序列中某个值。因为如果 $v$ 在两值之间，将其调整至较小的那个值，分子不变，$v$ 变得更小。 由于 $k$ 不好遍历求解，所以我们遍历 $v$，希望对于每一个 $v$ 求出所有序列长度的平方和。 从而发现如果从小到大考虑每一个 $v$，已加入序列的数字不会再退出，所以我们可以用**并查集**维护**所有已加入序列的数所在的序列**，然后递推求解分子和 $k$。 具体来说，每次加入一个新的 $v$，无外乎三种情况： 1.$v$ 的两侧数都没有加入，此时 $k\leftarrow k+1,sum\leftarrow sum+1$。 2.$v$ 的一侧数已加入，不妨设为左侧，此时 $sum\leftarrow sum+(|left|+1)^2-|left|^2$。 3.$v$ 的两侧数已加入，此时 $k\leftarrow k-1,sum\leftarrow sum+(|left|+|right|+1)^2-|left|^2-|right|^2$。 $v$ 的左右两侧区间大小可以在**维护并查集时记录在根节点上**。