首页 > 代码库 > cpdeforces 712 E. Memory and Casinos 概率论 + 线段树
cpdeforces 712 E. Memory and Casinos 概率论 + 线段树
给出一个数组p,长度为n,1 <= n <= 10^5
表示有n个格子,在第i个格子,你有p[i]的概率会到i + 1,有1 - p[i]的概率会到i - 1
如果在区间[l,r]上玩游戏,我们规定你起点在l,然后你开始走,
如果你到了l - 1,那么你失败了,游戏结束
如果你到了r + 1,那么你成功了,游戏结束
现在有q个操作,1 <= q <= 10^5
1 i a b 修改p[i] = (double)a / b
2 l r 询问在[l,r]上玩游戏,成功的概率
看这道题目,我们首先反应就是线段树,那要维护什么?
我们先来看看在[l,r]上玩游戏,
令f(i)表示从i开始,到r + 1的概率,即游戏成功的概率
我们要求的就是f(l)
显然,f(l - 1) = 0,f(r + 1) = 1
对l <= i <= r,f(i) = p[i] * f(i + 1) + (1 - p[i]) * f(i - 1)
则 f(i) - f(i - 1) = p[i] * f(i + 1) - p[i] * f(i - 1)
令g(i) = f(i) - f(i - 1)
(我们要求f(l),由于g(l) = f(l) - f(l - 1) = f(l),所以我们要求的变成了g(l))
则g(i) = p[i] * (g(i + 1) + g(i))
令u[i] - (1 - p[i]) / p[i]
则g(i + 1) = u[i] * g(i)
发现g(l) + g(l + 1) + ... + g(r + 1) = 1
即g(l) = 1 / (1 + u[l] + u[l] * u[l + 1] + ... + u[l] * u[l + 1] * ... * u[r] )
所以,如果我们用一颗线段树,叶子节点i的值前缀积u[1] * u[2] * .. * u[i]
然后维护区间和
那么对于每一个询问[l,r],要求g(l)
如果l = 1,g(l) = 1 / (1 + query(1,r,1,n,1))
如果l > 1,g(l) = query(l-1,l-1,1,n,1) / query(l-1,r,1,n,1)
然后修改操作在这里就是区间修改了
可以了
但是,这样子会被卡精度,我就被卡了
怎么改:
线段树维护2个值,
如果一个节点代表的区间是[l,r]那么这个节点维护
u[l] + u[l] * u[l + 1] + ... + u[l] * ... * u[r] 和
u[l] * ... * u[r]
那么合并2个子节点也很简单
同时修改操作成了单点修改啦
这样子就可以过了
cpdeforces 712 E. Memory and Casinos 概率论 + 线段树