$freeway$
$ps:$ 有点毒的线段树加概率期望，感觉大致有点理解了概率期望的含义，跟平均数有点像？计数就是把所有答案的和除以方案个数。
还有一个小套路？下面讲。
$Description$
$Solution$
区间求和，区间查询，显然是线段树题。
然后我们考虑如何进行区间查询。
先考虑求 $l \to r$ 的花费，用一个前缀和数组 $sum$ 记一下，显然花费就是 $sum_r - sum_{l + 1}$ 。
所以期望就是
$$
\dfrac{\sum_{i = l}^{r}\sum_{j = i}^{r}(sum_j - sum_i)}{C_{r - l + 1}^{2}}
$$
然后我们考虑如何求出上面这个式子。
分母显然就是 $(r - l + 1) \times (r - l) / 2$ ，然后我们考虑如何求分子。
然后就用到一个推导套路 (?) ，对于区间 $[l, r]$ ，考虑枚举区间内每个数被包含了多少次。
比如
$$
l \in [l, l], [l, l + 1] \ldots ,[l, r]
$$
所以分子就是
$$
\sum_{i = l}^{r}a_i \times (r - i + 1) \times (i - l + 1)
$$
然后把他拆开，再化简
$$
\sum_{i = l}^{r}a_i\times(i\times(l + r) + (-i^2) + (r - l + 1 - rl))
$$
即
$$
\sum_{i = l}^{r}a_i\times(r - l + 1 - rl) + \sum_{i = l}^{r}i \times (l + r) + \sum_{i = l}^{r}(-i^2)
$$
线段树维护 $\sum_{i = l}^{r}a_i, \sum_{i = l}^{r}a_i \times i, \sum_{i = l}^{r} \times a_i \times i^2$ 这三个东西就好了。
然后考虑如何维护。
假如现在对于一段区间加上一个 $v$ ，那么
$$
sum_1 += (r - l + 1) \times v
$$
$$
sum_2 += ((l + r) \times (r - l + 1) / 2) \times v
$$
$$
sum_3 += \frac{r(r + 1)(2r + 1) - l(l - 1)(2l - 1)}{6} \times v
$$
线段树即可。
$ps:$ 第三个就是用到了求 $\sum_{i = 1}^{n}i^2$ 的公式，即 $\dfrac{n(n + 1)(2n + 1)}{6}$ 。
$Code:$
1 |
|