$ \begin{aligned}ans &= \frac{\binom{num_l}{2} + \binom{num_{l + 1}}{2} + \dots + \binom{num_r}{2}}{\binom{r - l + 1}{2}} \\ &= \frac{num_l(num_l - 1) + num_{l + 1}(num_{l + 1} - 1) + \dots + num_r(num_r - 1)}{(r - l + 1)(r - l)} \\ &= \frac{(num_l^2 + num_{l + 1}^2 + \dots + num_r^2) - (num_l + num_{l + 1} + \dots + num_r)}{(r - l + 1)(r - l)} \\ &= \frac{(num_l^2 + num_{l + 1}^2 + \dots + num_r^2) - (r - l + 1)}{(r - l + 1)(r - l)} \end{aligned} $

而

$ (n + 1)^2 = n^2 + 1 + 2n \\ (n - 1)^2 = n^2 + 1 - 2n $

所以对于每一个询问 $[l, r]$，我们只需要将当前询问的分子加上 $2n + 1$ 即可 $O(1)$ 地将答案扩展至 $[l, r + 1]$ 或 $[l - 1, r]$，而对于缩小区间的操作，同理。

于是，我们可以用 $\mid l' - l \mid + \mid r' - r \mid$ 次操作转移至下一询问区间。

而利用分块，将所处分块作为第一关键字，将右区间作为第二关键字，可以实现 $O(n \sqrt n)$ 的时间复杂度。