题解
解法1:(官方做法)
一段区间的(L)定义为从最左边开始出发,最左不失败,一直到最右边胜利的概率,(R)定义为从最右边开始出发,最左不失败,又回到最右边胜利的概率
考虑一个区间([l, r])记为(u),左右儿子([l, mid])和([mid + 1, r])分别记为(ls)和(rs)
枚举一下(mid)和(mid+1)之间往返多少次
这玩意是无穷项等比数列求和:
(u.R)分不过和过(mid)两种情况
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
struct node {
double L, R;
void rd() {
int x, y;
scanf("%d%d", &x, &y);
L = R = x * 1.0 / y;
}
} a[N << 2];
int n, q;
node operator + (const node &ls, const node &rs) {
node ans;
ans.L = ls.L * rs.L / (1 - ls.R * (1 - rs.L));
ans.R = rs.R + (1 - rs.R) * rs.L * ls.R / (1 - ls.R * (1 - rs.L));
return ans;
}
void build(int rt, int l, int r) {
if(l == r) {
a[rt].rd();
return ;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
a[rt] = a[rt << 1] + a[rt << 1 | 1];
}
void modify(int rt, int l, int r, int x, double p) {
if(l == r) {
a[rt].L = a[rt].R = p;
return ;
}
int mid = (l + r) >> 1;
if(x <= mid) modify(rt << 1, l, mid, x, p);
else modify(rt << 1 | 1, mid + 1, r, x, p);
a[rt] = a[rt << 1] + a[rt << 1 | 1];
}
node query(int rt, int l, int r, int ql, int qr) {
if(l == ql && r == qr) return a[rt];
int mid = (l + r) >> 1;
if(qr <= mid) return query(rt << 1, l, mid, ql, qr);
if(ql > mid) return query(rt << 1 | 1, mid + 1, r, ql, qr);
return query(rt << 1, l, mid, ql, mid) + query(rt << 1 | 1, mid + 1, r, mid + 1, qr);
}
int main() {
scanf("%d%d", &n, &q);
build(1, 1, n);
int op, x, y, z;
while(q --) {
scanf("%d%d%d", &op, &x, &y);
if(op == 1) {
scanf("%d", &z);
modify(1, 1, n, x, y * 1.0 / z);
}
if(op == 2) {
printf("%.10f
", query(1, 1, n, x, y).L);
}
}
return 0;
}
解法2:
(dp[i])表示从(i)开始成功的概率
令(dp[l - 1] = 0, dp[r + 1] = 1),则(dp[i] = dp[i - 1] * (1 - p[i]) + dp[i + 1] * p[i])
化简得:(dp[i] - dp[i - 1] = p[i] * (dp[i + 1] - dp[i - 1]))
令(d[i] = dp[i] - dp[i - 1])
(d[i] = p[i] * (d[i + 1] + d[i]))
解得:(d[i + 1] = frac{1 - p[i]}{p[i]} d[i])
为了简便,令(u[i] = frac{1 - p[i]}{p[i]})
则递推式为(d[i + 1] = u[i] * d[i])
考虑我们怎么求(dp[l])(即(d[l]))
(d[l] + d[l+1] + ... + d[r + 1] = dp[r + 1] - dp[l] = 1)
所以(d[l] (1 + u[l] + u[l] * u[l + 1] + ... + u[l] * u[l + 1] * u[l + 2] * .. * u[r]) = 1)
(d[l] = frac{1}{1 + u[l] + u[l] * u[l + 1] + ... + u[l] * u[l + 1] * u[l + 2] * .. * u[r]})
线段树维护两个东西,一个是(u)的乘积,一个是所有前缀的乘积和,就做完了
代码就不写了