思路
线段树,对于每个节点维护两个值。一个是当前区间从左边进入,从右边出去的概率,记为$val1$;一个是当前区间从右边进入,从右边出去的概率,记为$val2$。
考虑如何合并,记$l_1, r_1$分别为左儿子的$val1, val2$,$l_2, r_2$分别为右儿子的$val1, val2$,$L, R$分别为自己的$val1, va2$
如果从左儿子左边进入,直接从右儿子右边右边出去,概率为$l_1\cdot l_2$
从左儿子左边进入,到右儿子,又回到左儿子,又到右儿子,最终从右儿子右边出去,概率为$l_1\cdot (1-l_2)\cdot r_1\cdot l_2$
以此类推,剩下的式子为
$$l_1\cdot ((1-l_2)\cdot r_1)^2\cdot l_2$$
$$l_1\cdot ((1-l_2)\cdot r_1)^3\cdot l_2$$
$$\dots$$
$$l_1\cdot ((1-l_2)\cdot r_1)^{\infty}\cdot l_2$$
相加可得$$L=\frac{l_1\cdot l_2}{1-(1-l_2)\cdot r_1}$$
同理
$$R=r_2+\frac{l_2\cdot r_2\cdot (1-r_2)}{1-(1-l_2)\cdot r_1}$$
询问和修改都是普通的操作了
代码
#include <iostream>
#include <cstdio>
#define pdd std::pair<double, double>
#define mp std::make_pair
int n, q;
class SegTree{
private:
struct Node{
int l, r;
double val1, val2;
Node *lch, *rch;
Node(int l, int r, Node *lch, Node *rch) :
l(l), r(r), lch(lch), rch(rch){}
void push_up(){
val1=lch->val1*rch->val1/(1-(1-rch->val1)*lch->val2);
val2=rch->val2+rch->val1*lch->val2*(1-rch->val2)/(1-(1-rch->val1)*lch->val2);
}
}*root;
pdd merge(pdd x, pdd y){
pdd ans;
ans.first=x.first*y.first/(1-(1-y.first)*x.second);
ans.second=y.second+y.first*x.second*(1-y.second)/(1-(1-y.first)*x.second);
return ans;
}
Node *build(int l, int r){
Node *v;
if(l==r){
int a, b;
scanf("%d%d", &a, &b);
v=new Node(l, r, NULL, NULL);
v->val1=v->val2=(double)a/b;
return v;
}
v=new Node(l, r, build(l, (l+r)/2), build((l+r)/2+1, r));
v->push_up();
return v;
}
void modify(Node *v, int p, double val){
if(v->l==v->r){
v->val1=v->val2=val;
return;
}
if(2*p<=v->l+v->r) modify(v->lch, p, val);
else modify(v->rch, p, val);
v->push_up();
}
pdd query(Node *v, int l, int r){
if(l<=v->l && v->r<=r){
return mp(v->val1, v->val2);
}
int mid=(v->l+v->r)/2;
if(l<=mid && r>mid)
return merge(query(v->lch, l, r), query(v->rch, l, r));
if(l<=mid) return query(v->lch, l, r);
if(r>mid) return query(v->rch, l, r);
}
public:
SegTree(){
root=build(1, n);
}
void modify(int p, int a, int b){
modify(root, p, (double)a/b);
}
double query(int l, int r){
return query(root, l, r).first;
}
};
int main(){
int opt, l, r, p, a, b;
scanf("%d%d", &n, &q);
SegTree *T=new SegTree;
while(q--){
scanf("%d", &opt);
if(opt==1){
scanf("%d%d%d", &p, &a, &b);
T->modify(p, a, b);
}else{
scanf("%d%d", &l, &r);
printf("%lf\n", T->query(l, r));
}
}
return 0;
}