设\(f[i]\)为从\(i\)到\(r+1\)且不走出区间的概率

\(f[i]=p[i]f[i+1]+(1-p[i])f[i-1]\)

\(f[i]-f[i-1]=p[i](f[i+1]-f[i-1])\)

\(f[r+1]=1,f[l-1]=0\)

\(g[i]=f[i]-f[i-1]\)

\(g[i]=p[i](g[i+1]+g[i])\)

\(g[i+1]=\frac{1-p[i]}{p[i]} g[i]\)

\(\sum_{i=l}^{r+1} g[i]=f[r+1]-f[l-1]=1\)

\(lis[l][r]=\sum_{i=l}^{r} \prod_{j=l}^i \frac{1-p[j]}{p[j]}\)

\(f[l]=g[l]=\frac{1}{lis[l][r]+1}\)

线段树维护前缀积、前缀和即可

#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1<<17;int n,m;int ik[MAXN];double sum[2][MAXN<<1];struct rpg{double a,b;};int read(){    int x=0;char ch=getchar();    while(ch<'0'||'9'
    
     >1;    build(i,l,mid),build(i|1,mid+1,r);    return;}void cchg(int k,double v){    sum[0][k]=sum[1][k]=v;k>>=1;    while(k){        int i=k<<1;        sum[0][k]=sum[0][i]*sum[0][i|1];        sum[1][k]=sum[1][i]+sum[0][i]*sum[1][i|1];        k>>=1;    }return;}rpg cask(int k,int l,int r,int le,int ri){    if(le<=l&&r<=ri) return (rpg){sum[0][k],sum[1][k]};    int i=k<<1,mid=l+r>>1;    if(le<=mid&&mid