CF 712E

思路

线段树，对于每个节点维护两个值。一个是当前区间从左边进入，从右边出去的概率，记为$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;
}