当前位置: 代码迷 >> 综合 >> codeforces712E Memory and Casinos(区间树)
  详细解决方案

codeforces712E Memory and Casinos(区间树)

热度:93   发布时间:2024-01-16 13:28:19.0

题意:

有n个赌场,你在i赌场时,有pi的概率走到i+1,有1?pi的概率走到i?1.保证任何时候pi≤pi+1
有q次操作,修改一个赌场的p值;或者询问[l,r]表示从第l个赌场走到r的概率,他在走的过程中不会离开区间[l,r].

要点:

比较容易看出是区间树,但是这个概率的处理很复杂,基本思路可以参考下面这个博客:

参考博客:点击打开链接

但是这个博客还有网上我找了一下,有一个地方都没有解释,就是最后结果应该是:

f[l]/f[r]=(g[1]+g[2]...g[l])/(g[1]+g[2]...g[r])=g[1]*(1+t1+t1*t2+...)/(g[1]*((1+t1+t1*t2+...))=(1+t1+t1*t2+...t1*t2..tl)/(1+t1+t1*t2+...t1*t2*tl)=1+(tl+tl*tl+1...)

最后用区间树维护一下即可。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 100005;
struct segtree
{double a, b;
}seg[4*maxn],now;
double p[maxn];
int n, q;void build(int l, int r, int pos)
{if (l == r){seg[pos].a = seg[pos].b = (1 - p[l]) / p[l];return;}int mid = (l + r) / 2;build(l, mid, pos*2);build(mid+1, r, pos * 2 + 1);seg[pos].a = seg[2 * pos].a*seg[2 * pos + 1].a;seg[pos].b = seg[2 * pos].b + seg[2 * pos].a*seg[2 * pos + 1].b;
}
void query(int l, int r, int x, int y, int pos)
{if (l == x&&r == y){now.b = now.b + now.a*seg[pos].b;now.a = now.a*seg[pos].a;return;}int mid = (l + r) / 2;if (y <= mid) query(l, mid, x, y, pos * 2);else if (x > mid) query(mid + 1, r, x, y, pos * 2 + 1);else{query(l, mid, x, mid, pos * 2);query(mid + 1, r, mid + 1, y, pos * 2 + 1);}
}
void update(int l, int r, int pos, int x)
{if (l == r){seg[pos].a = seg[pos].b = (1 - p[l]) / p[l];return;}int mid = (l + r) / 2;if (x <= mid)update(l, mid, 2 * pos, x);elseupdate(mid+1, r, 2 * pos + 1, x);seg[pos].a = seg[2 * pos].a*seg[2 * pos + 1].a;seg[pos].b = seg[2 * pos].b + seg[2 * pos].a*seg[2 * pos + 1].b;
}int main()
{int a, b;cin >> n >> q;for (int i = 1; i <= n; i++){cin >> a >> b;p[i] = 1.0*a/b;}build(1, n, 1);while (q--){int order, x, y,z;cin >> order;if (order == 2){cin >> x >> y;now.a = 1;now.b = 0;query(1, n, x, y, 1);double ans;if (now.b <= 1e15)ans = 1 / (1 + now.b);elseans = 0;printf("%.10lf\n", ans);}else{	cin >> x >> y >> z;p[x] = 1.0*y/z;update(1, n, 1, x);}}return 0;
}


  相关解决方案