思路与题解

把所有相同取值聚合。设 $U=\max(x_i)$，定义频次数组 $cnt[x]$ 表示值为 $x$ 的元素个数。则

$H$=$\sum_{y=1}^{U} cnt[y]\cdot H(y)$,$\quad$

$H(y)$=$\sum_{x=1}^{U} cnt[x]$ $\cdot \left\lfloor \dfrac{x}{y}\right\rfloor.$

对固定的 $y$，当 $x\in [ky,(k+1)y-1]$ 时有 $\left\lfloor \dfrac{x}{y}\right\rfloor$=$k$。因此可以把 $[1,U]$ 按长度为 $y$ 的区间分块：