题目大意:$n$个点, 每个点$i$有成功率$p_i$, 若成功走到$i+1$, 否则走到走到$i-1$, 多组询问, 求从$l$出发, 在$l$处不失败, 最后在$r$处胜利的概率
设$L[l,r]$表示从$l$出发, 在$l$处不失败, 最后在$r$处胜利的概率,$R[l,r]$表示从$r$出发, 在$l$处不失败, 最后在$r$处胜利的概率
记$l_1=L[l,mid],r_1=L[mid+1,r],l_2=R[l,mid],r_2=R[mid+1,r].$
枚举在$mid$到$mid+1$之间往返的次数, 可以得到下式
$$L[l,r]=l_1l_2\sum\limits_{n=0}^\infty{(1-l_2)^nr_1^n}=\frac{l_1l_2}{1-(1-l_2)r_1}$$
$$R[l,r]=r_2+(1-r_2)r_1l_2\sum\limits_{n=0}^\infty{(1-l_2)^nr_1^n}$$
$$=r_2+(1-r_2)\frac{r_1l_2}{1-(1-l_2)r_1}$$
直接用线段树维护就好了
还有另外一种做法, 考虑询问$[l,r]$
设$f_i$表示从$i$走到$r$且在$r$处胜利的概率, 则答案即为$f_l$
规定$f_{l-1}=0,f_{r+1}=1$ 就有$f_i=(1-p_i)f_{i-1}+p_if_{i+1}$
即$f_i-f_{i-1}=p_i(f_{i+1}-f_{i-1})$
令$g_i=f_i-f_{i-1}$ 则有$g_i=p_i(g_{i+1}-g_{i})$
记$a_i=\frac{1}{p_i}-1,$ 可以得到$g_{i+1}=a_ig_i$
由于$\sum_{i=l}^{r+1}{g_i}=1$
所以就可以得到$f_l=g_l=\frac{1}{1+a_l+a_la_{l+1}+...+a_la_{l+1}\cdot \cdot \cdot a_{r}}$
记$A[l,r]=\prod_{i=l}^{r}{a_i}, B[l,r]=\sum_{i=l}^{r}{A_i}$
有$$A[l,r]=A[l,mid]A[mid+1,r]$$
$$B[l,r]=B[l,mid]+A[l,mid]B[mid+1,r]$$
线段树维护$A,B$即可
第一种代码
#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc (lc|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
using namespace std; const int N = 1e5+;
int n, m;
struct _ {
double L, R;
_ () {}
_ (int x, int y) {L=R=(double)x/y;}
_ (double l,double r) :L(l),R(r) {}
_ operator + (const _ &rhs) const {
return _(L*rhs.L/(-(-rhs.L)*R),rhs.R+(-rhs.R)*R*rhs.L/(-(-rhs.L)*R));
}
} v[N<<]; void build(int o, int l, int r) {
if (l==r) {
int x, y;
scanf("%d%d", &x, &y);
v[o]=_(x,y);
return;
}
build(ls),build(rs),v[o]=v[lc]+v[rc];
} void upd(int o, int l, int r, int pos, int x, int y) {
if (l==r) return v[o]=_(x,y),void();
if (mid>=pos) upd(ls,pos,x,y);
else upd(rs,pos,x,y);
v[o]=v[lc]+v[rc];
} _ qry(int o, int l, int r, int ql, int qr) {
if (ql<=l&&r<=qr) return v[o];
if (mid<ql) return qry(rs,ql,qr);
if (mid>=qr) return qry(ls,ql,qr);
return qry(ls,ql,qr)+qry(rs,ql,qr);
} int main() {
scanf("%d%d", &n, &m);
build(,,n);
REP(i,,m) {
int op, pos, a, b;
scanf("%d", &op);
if (op==) {
scanf("%d%d%d", &pos, &a, &b);
upd(,,n,pos,a,b);
} else {
scanf("%d%d", &a, &b);
printf("%.12lf\n", qry(,,n,a,b).L);
}
}
}
第二种完全类似, 改下公式就行了
#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc (lc|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
using namespace std; const int N = 1e5+;
int n, m;
struct _ {
double A, B;
_ () {}
_ (int x, int y) {A=B=(double)y/x-;}
_ (double a,double b) :A(a),B(b) {}
_ operator + (const _ &rhs) const {
return _(A*rhs.A,B+A*rhs.B);
}
} v[N<<]; void build(int o, int l, int r) {
if (l==r) {
int x, y;
scanf("%d%d", &x, &y);
v[o]=_(x,y);
return;
}
build(ls),build(rs),v[o]=v[lc]+v[rc];
} void upd(int o, int l, int r, int pos, int x, int y) {
if (l==r) return v[o]=_(x,y),void();
if (mid>=pos) upd(ls,pos,x,y);
else upd(rs,pos,x,y);
v[o]=v[lc]+v[rc];
} _ qry(int o, int l, int r, int ql, int qr) {
if (ql<=l&&r<=qr) return v[o];
if (mid<ql) return qry(rs,ql,qr);
if (mid>=qr) return qry(ls,ql,qr);
return qry(ls,ql,qr)+qry(rs,ql,qr);
} int main() {
scanf("%d%d", &n, &m);
build(,,n);
REP(i,,m) {
int op, pos, a, b;
scanf("%d", &op);
if (op==) {
scanf("%d%d%d", &pos, &a, &b);
upd(,,n,pos,a,b);
} else {
scanf("%d%d", &a, &b);
printf("%.12lf\n", /(+qry(,,n,a,b).B));
}
}
}