题解：P5012 水の数列

一道很好的数据结构题。

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

$T$ 次询问，每次给出 $l,r$，试求 $\max_{l \leq i \leq r}d(i)$。

我们将题意整理成现在这样，意在展示只要求出每一个 $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$ 的左右两侧区间大小可以在维护并查集时记录在根节点上。