题目链接
题目描述
有一个长度为 \(n\) 的01序列，第 \(i\) 个位置有 \(p_i\) 的概率为1，对于上面的一段 \(l\sim r\) 的区间，现在有两种计算方式（\(A,B,t\) 都是给定的值）：
\[\text{基本分}=A\times\sum_{i=l}^r s_i\\
\text{毗连分}=B\times(\sum_{i=l}^r s_i\cdot f(i))\\
f(i) =
\begin{cases}
s_i & i = l \\
f(i-1) + 1 & i \neq l \land S_i = 1 \\
f(i-1) \times t & \text{otherwise}
\end{cases}
\]
现在你需要支持两种操作，单点修改概率 和 区间求基本分与毗连分的和的期望。
\(n,q\le 5\times10^5\)
题解
有期望的线性性可以拆成基本分和毗连分两个分别算期望，基本分非常好算：
\[E[\text{基本分}]=E[A\times\sum_{i=l}^r s_i]=A\times\sum_{i=l}^r p_i
\]
这个显然可以用树状数组维护。
毗连分比较困难：
\[E[\text{毗连分}]=B\times(\sum_{i=l}^r f(i)\cdot p_i)
\]
考虑将其拆成贡献形式，我们发现 \(i,j(i\le j)\) 之间是一个只有 \(t\) 的一个若干次多项式，我们钦定 \(i,j\) 是1来统计答案，我们只考虑从 \(i\) 开始的 \(t\) 到 \(j\) 的贡献，考虑在 \([i+1,j-1]\) 这段区间的数，如果为1，则贡献 \(\times 1\)，否则可以 \(\times t\)，于是枚举 \(i,j\) 统计贡献，可以写出这样的式子：
\[\sum_{i=l}^r\sum_{j=i+1}^rp_ip_j\prod_{k=i+1}^{j-1}g_k\\
g_k=p_k\times1+(1-p_k)\times t。
\]
附注：这里只考虑从当前的 \(i\) 到 \(j\) 单项 \(t\) 的贡献，其他项的贡献在枚举其他 \(i,j\) 是自然会统计。