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

àì夳堔傛蜴生んèń 2021-11-16 09:08 300阅读 0赞

**题解**

**解法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 <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\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\\)