题意：(n)个赌场，每个赌场有(p_{i})的胜率，如果赢了就走到下一个赌场，输了就退回上一个赌场，规定(1)号赌场的上一个是(0)号赌场，(n)号赌场的下一个是(n + 1)号赌场，一旦到达(0)或(n + 1)号赌场就相当于退出赌局了。
定义统治区间([l, r])为从第(l)个赌场开始，到达第(r + 1)个赌场，且在过程中不经过([1, l - 1])的赌场。维护2种操作：
1，修改一个赌场的胜率
2，询问统治([l, r])的概率
题解：
设(f_{i})表示从(x)能走到(n)的概率，则有：
令(g_{i} = f_{i} - f_{i - 1} = p_{i} (g_{i} + g_{i + 1}))(由上式得)
所以(g_{i + 1} = g_{i} cdot frac{1 - p_{i}}{p_{i}}),
令(t_{i} = frac{1 - p_{i}}{p_{i}}),则(g_{i + 1} = g_{i} t_{i})
显然有(f_{n} = 1(不用走就到了), f_{0} = 0(因为已经出边界)).
所以(sum_{i = 1}^{n}g_{i} = 1)，那么带入上面(g_{i + 1} = g_{i} t_{i}),得到：
提出(g_{1}).
那么我们维护(t)值，就可以得到(g_{1})的值。
上面是求询问区间([1, n - 1])时的答案，也就是(1)到(n)的概率。
替换一下，同理可得，在询问区间([l, r])时，也就是要求(l)到(r + 1)的概率，那么就有如下等式：
用线段树维护:
对于区间([l, r])维护(t_{l} + t_{l}t_{l + 1} + ... + t_{l}t_{l + 1}...t_{r}).然后在最后加1即可。
定义node结构体，其中x表示这个区间的(t_{l} + t_{l}t_{l + 1} + ... + t_{l}t_{l + 1}...t_{r})，w表示(t_{l}t_{l + 1}...t_{r})
那么合并时新区间的x为(left.x + right.x * left.w),
w为(left.w cdot right.w)
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 101000
#define ac 500000
int n, q, w;
int l[ac], r[ac];
double ans, go;
double tree[ac], p[AC], t[AC], sum[ac];
struct node{
double x, w;
};
inline int read()
{
int x = 0;char c = getchar();
while(c > '9' || c < '0') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
inline void update(int x){
int ll = x * 2, rr = ll + 1;
sum[x] = sum[ll] * sum[rr];
tree[x] = tree[ll] + tree[rr] * sum[ll];
}
void build(int x, int ll, int rr)
{
l[x] = ll, r[x] = rr;
if(ll == rr) {tree[x] = sum[x] = t[ll]; return ;}
int mid = (ll + rr) >> 1;
build(x * 2, ll, mid), build(x * 2 + 1, mid + 1, rr);
update(x);
}
void change(int x, int go, double w)
{
if(l[x] == r[x]){sum[x] = tree[x] = w; return ;}
int mid = (l[x] + r[x]) >> 1;
(go <= mid) ? change(x * 2, go, w) : change(x * 2 + 1, go, w);
update(x);
}
node find(int x, int ll, int rr)
{
if(l[x] == ll && r[x] == rr) return (node){tree[x], sum[x]};
int mid = (l[x] + r[x]) >> 1;
if(rr <= mid) return find(x * 2, ll, rr);
else if(ll > mid) return find(x * 2 + 1, ll, rr);
else
{
node now = find(x * 2, ll, mid), y = find(x * 2 + 1, mid + 1, rr);
now.x = now.x + y.x * now.w, now.w = now.w * y.w;//要更新now.w!!!
return now;
}
}
void pre()
{
n = read(), q = read();
for(R i = 1; i <= n; i ++)
{
double a = read(), b = read();
p[i] = a / b;
}
for(R i = 1; i <= n; i ++) t[i] = (1 - p[i]) / p[i];
}
void work()
{
int opt, a, b, x;
for(R i = 1; i <= q; i ++)
{
opt = read();
if(opt == 1)
{
x = read(), a = read(), b = read(), go = 1.0 * a / b;
go = (1 - go) / go, change(1, x, go);
}
else
{
a = read(), b = read();
node x = find(1, a, b);
// printf("%lf
", x.x);
printf("%.10lf
", 1 / (1 + x.x));
}
}
}
int main()
{
freopen("in.in", "r", stdin);
pre();
build(1, 1, n);
work();
fclose(stdin);
return 0;
}