首页 > 代码库 > 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 概率论 + 线段树