ABC332F Random Update Query 题解
在学校打的，切 ABCF 直接摆烂，D 题暴搜调不出来，很难蚌。
给你一个序列 \(a_i\)，\(m\) 次操作，第 \(i\) 次将 \([l_i,r_i]\) 区间内等概率随机的一个数修改为 \(x_i\)，最后求每个数值的期望。
假定一个元素，当前的期望是 \(a\)，考虑执行一个参数为 l r x 的修改。
那么它有 \(\frac{1}{r-l+1}\) 概率被修改为 \(x\)，有 \(\frac{r-l}{r-l+1}\) 概率不变。则新的期望 \(\frac{r-l}{r-l+1}\times a+\frac{x}{r-l+1}\)。
注意到这相当于乘上 \(\frac{r-l}{r-l+1}\) 再加上 \(\frac{x}{r-l+1}\)，线段树可做，和 线段树2 本质相同。
时间复杂度 \(O(n \log n + m \log n)\)。只求了 \(r-l+1\) 的逆元，所以逆元复杂度是 \(O(\log n)\)。
标签：期望,ABC332F,复杂度,逆元,frac,log From： https://www.cnblogs.com/C01et10n/p/17957962