题库-CF|【Codeforces Round 370 (Div 2) E】【线段树等比数列区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率数据结构-线段树|数学-多项式

E. Memory and Casinos time limit per test 4 seconds memory limit per test 512 megabytes input standard input output standard output There are n casinos lined in a row. If Memory plays at casino i, he has probability pi to win and move to the casino on the right (i?+?1) or exit the row (if i?=?n), and a probability 1?-?pi to lose and move to the casino on the left (i?-?1) or also exit the row (if i?=?1).
We say that Memory dominates on the interval i... j if he completes a walk such that,

He starts on casino i.
He never looses in casino i.
He finishes his walk by winning in casino j.

Note that Memory can still walk left of the 1-st casino and right of the casino n and that always finishes the process.
Now Memory has some requests, in one of the following forms:

1 i a b: Set
文章图片
.
2 l r: Print the probability that Memory will dominate on the interval l... r, i.e. compute the probability that Memory will first leave the segment l... r after winning at casino r, if she starts in casino l.

It is guaranteed that at any moment of time p is a non-decreasing sequence, i.e. pi?≤?pi?+?1 for all i from 1 to n?-?1.
Please help Memory by answering all his requests!
Input The first line of the input contains two integers n and q(1?≤?n,?q?≤?100?000),— number of casinos and number of requests respectively.
The next n lines each contain integers ai and bi (1?≤?ai?bi?≤?109)—

题库-CF|【Codeforces Round 370 (Div 2) E】【线段树等比数列区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率

文章图片
is the probability pi of winning in casino i.
The next q lines each contain queries of one of the types specified above (1?≤?a?b?≤?109, 1?≤?i?≤?n, 1?≤?l?≤?r?≤?n).
It's guaranteed that there will be at least one query of type 2, i.e. the output will be non-empty. Additionally, it is guaranteed that p forms a non-decreasing sequence at all times.
Output Print a real number for every request of type 2 — the probability that boy will "dominate" on that interval. Your answer will be considered correct if its absolute error does not exceed 10?-?4.
Namely: let's assume that one of your answers is a, and the corresponding answer of the jury is b. The checker program will consider your answer correct if |a?-?b|?≤?10?-?4.
Example input

3 13 1 3 1 2 2 3 2 1 1 2 1 2 2 1 3 2 2 2 2 2 3 2 3 3 1 2 2 3 2 1 1 2 1 2 2 1 3 2 2 2 2 2 3 2 3 3

output

0.3333333333 0.2000000000 0.1666666667 0.5000000000 0.4000000000 0.6666666667 0.3333333333 0.2500000000 0.2222222222 0.6666666667 0.5714285714 0.6666666667

【题库-CF|【Codeforces Round 370 (Div 2) E】【线段树等比数列区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率】

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x,y) memset(x,y,sizeof(x)) #define MC(x,y) memcpy(x,y,sizeof(x)) #define MP(x,y) make_pair(x,y) #define ls o<<1 #define rs o<<1|1 #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define ff first #define ss second typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; typedef pair PD; template inline void gmax(T1 &a, T2 b) { if (b>a)a = b; } template inline void gmin(T1 &a, T2 b) { if (b> 1; build(lson); build(rson); a[o] = merge(a[ls], a[rs]); } PD V; int P; void update(int o, int l, int r) { if (l == r) { a[o] = V; return; } int mid = (l + r) >> 1; if (P <= mid)update(lson); else update(rson); a[o] = merge(a[ls], a[rs]); } int L, R; PD query(int o, int l, int r) { if (l >= L&&r <= R)return a[o]; int mid = (l + r) >> 1; if (R <= mid)return query(lson); else if (L > mid)return query(rson); else return merge(query(lson), query(rson)); } int main() { while (~scanf("%d%d", &n, &q)) { build(1, 1, n); while (q--) { int op; scanf("%d", &op); if (op == 1) { double x, y; scanf("%d%lf%lf", &P, &x, &y); V = { x / y,x / y }; update(1, 1, n); } else { scanf("%d%d", &L, &R); printf("%.12f\n", query(1, 1, n).ff); } } } return 0; } /* 【题意】有n（1e5）个赌场，我们一开始在1号赌场，在第i个赌场赌赢的概率为p[i] 如果赌赢了，会进入第i+1个赌场如果赌输了，会进入第i-1个赌场有m（1e5）个询问，问你，对于询问区间[l,r] 如果我们从l位置开始赌博，第一次走出[l,r]区间是因为r赢而不是因为l输的概率是多少。【类型】线段树等比数列区间合并【分析】我们要求的是对于区间[l,r]，从l位置开始赌博，第一次走出[l,r]区间是因为r赢而不是因为l输的概率是多少。我们设其为L[l,r]，显然第一次是从[l,r]的l输走出区间的概率是1-L[l,r]这个问题乍一想很难，但是我们可以从中捕捉到区间合并的影子。我们考虑已经直到了[l,mid]和[mid+1,r]两个区间内部的属性，并尝试合并。我们把L[l,mid]设为l1,把L[mid+1,r]设为l2. 那么，我们考虑从mid->mid+1经过了1次，2次，3次，... 其概率公式分别是 l1 * l2 l1 * (1-l2) * probability of [ mid处进入[l,mid],mid处第一次出[l,mid]]于是我们需要: 对于区间[l,r]，从r位置开始赌博，第一次走出[l,r]区间是因为r赢而不是因为l输的概率为R[l,r]。把R[l,mid]设为r1,把R[mid+1,r]设为r2. 那么之前的概率公式变成了—— l1 * l2 l1 * (1-l2) * r1 * l2 l1 * ((1-l2) * r1)^2 * l2 ... a1=l1*l2 q=((1-l2)*r1) 无穷多项求和=a1/(1-q)我们还要求R 我们考虑从mid->mid+1经过了0次，1次，2次，3次，... 其概率公式分别是 r2 (1-r2) * r1 * l2 (1-r2) * r1 * (1 - l2) * r1 * l2 (1-r2) * r1 * ((1 - l2) * r1)^2 * l2 一样求和即可于是对于询问，我们可以用线段树维护区间L和R并合并，最后得到答案。【时间复杂度&&优化】 O(qlogn)*/