【Codeforces Round 370 (Div 2) E】【線段樹 等比數列 區間合并】Memory and Casinos 賭場區間[l,r] l進r先出的概率

16-09-29        來源：[db:作者]

E. Memory and Casinos time limit per test 4 seconds memory limit per test 512 megabytes input standard input output standard output

There arencasinos lined in a row. If Memory plays at casinoi, he has probabilitypito win and move to the casino on the right (i?+?1) or exit the row (ifi?=?n), and a probability1?-?pito lose and move to the casino on the left (i?-?1) or also exit the row (ifi?=?1).

We say that Memorydominateson the intervali...jif he completes a walk such that,

• He starts on casinoi.
• He never looses in casinoi.
• He finishes his walk by winning in casinoj.

Note that Memory can still walk left of the1-st casino and right of the casinonand that always finishes the process.

Now Memory has some requests, in one of the following forms:

• 1iab: Set .
• 2lr: Print the probability that Memory willdominateon the intervall...r, i.e. compute the probability that Memory will first leave the segmentl...rafter winning at casinor, if she starts in casinol.

It is guaranteed that at any moment of timepis anon-decreasing sequence, i.e.pi?≤?pi?+?1for allifrom1ton?-?1.

Input

The first line of the input contains two integersnandq(1?≤?n,?q?≤?100?000), — number of casinos and number of requests respectively.

The nextnlines each contain integersaiandbi(1?≤?ai?bi?≤?109) — is the probabilitypiof winning in casinoi.

The nextqlines 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 type2, i.e. the output will be non-empty. Additionally, it is guaranteed thatpforms a non-decreasing sequence at all times.

Output

Print a real number for every request of type2— the probability that boy will "dominate" on that interval. Your answer will be considered correct if its absolute error does not exceed10?-?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

#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;
}
/*
【題意】

【類型】

【分析】

l1 * l2
l1 * (1-l2) * probability of [ mid處進入[l,mid],mid處第一次出[l,mid]]

l1 * l2
l1 * (1-l2) * r1 * l2
l1 * ((1-l2) * r1)^2 * l2
...
a1=l1*l2
q=((1-l2)*r1)

r2
(1-r2) * r1 * l2
(1-r2) * r1 * (1 - l2) * r1 * l2
(1-r2) * r1 * ((1 - l2) * r1)^2 * l2

【時間復雜度&&優化】
O(qlogn)

*/