题解：序列期望

题目传送门
外网传送门

好，正片开始。

1. 期望的处理

根据代码源集训告诉我们， $\mathbb E=\frac{\text{总数}}{\text{方案数}}$，证明如下。

$$\mathbb E=P \times \text{收益}=\frac{1}{方案数} \times \text{总数}=\frac{\text{总数}}{\text{方案数}}$$

那么我们知道，方案数为 $∏_{i=1}^n r_i-l_i+1$，那么问题是如何求总数。

2. 总数

第一阶段，错误的尝试

我们考虑对于每个数的贡献，不难想到枚举 $h$，再看看在那个数取最大值，那么对于每一个数，就可以很轻松求出贡献，即

$$\sum_{i=\max\{h - r_i, 0\} + 1}^{h-l_i+1} i$$

为什么呢，我真的觉得很显然。

当 h <= r[i] 时

a[i]: ______l_____h__r
           最大   最小
并且取值连续。=> 等差数列求和

当 h > r[i] 时

a[i]:  ______l________r___h__
            max      min
并且取值连续。=> 等差数列求和

那么我们可以发现，这个公式与那个数取到最大值无关，所以我们可以去掉枚举最大值那一层循环，对于每一个数，都算一遍那个公式。最后看那个点取最大值，就不算那个点。这时，但是这却存在一个隐性错误。

第二阶段，去重

那么，我们发现，当有多个数取最大值时，这种情况会被多算，怎么办呢？

很显然，我们枚举最大值点时只考虑所有等于最大值的数中最右边的那个，例如：当 我取 3 3 1 3 2 时，我只在枚举到最后一个 3 时有贡献。

那么我们维护一个贡献前缀积与一个后缀积，前缀积包括最大值，后缀积不包含取到最大值，最后乘起来，总和呼之欲出。

如何计算不包含最大值，eh，其实就是当 $h \le r_i$ 时减一个 $1$.

那么，最后不要忘了除以方案数哦！！！