「CF712E」Memory and Casinos「线段树」「概率」-白红宇

「CF712E」Memory and Casinos「线段树」「概率」

阅读量：5162 次

发布时间：2019-06-13

本文共 2820 字，大约阅读时间需要 9 分钟。

题解

解法1：（官方做法）

一段区间的\(L\)定义为从最左边开始出发，最左不失败，一直到最右边胜利的概率，\(R\)定义为从最右边开始出发，最左不失败，又回到最右边胜利的概率

考虑一个区间\([l, r]\)记为\(u\)，左右儿子\([l, mid]\)和\([mid + 1, r]\)分别记为\(ls\)和\(rs\)

枚举一下\(mid\)和\(mid+1\)之间往返多少次

\[ u.L = ls.L * rs.L * \sum_{i = 0}^{\infty} ls.R^i(1-rs.L)^i \]

这玩意是无穷项等比数列求和：

\[u.L = \frac{ls.L * rs.L}{1 - ls.R * (1 - rs.L)}\]

\(u.R\)分不过和过\(mid\)两种情况

\[u.R = rs.R + (1 - rs.R)*rs.L*ls.R\sum_{i = 0}^{\infty} (1 - rs.L)^i ls.R^i\]

\[u.R = rs.R + (1 - rs.R)\frac{rs.L* ls.R}{1 - ls.R(1 - rs.L)}\]

#include 
    
     #include 
     
      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\n", 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\)