「CF712E」Memory and Casinos

发表于 分类于

题目链接：https://codeforces.com/problemset/problem/712/E。

考虑我们需要知道什么信息才能合并两个区间（把两个区间拼接起来）。

如果能快速做这个就直接线段树做完了。

考虑记录$x$表示能支配(dominate)这个区间的概率，$p$表示当前站在这个区间最后一个点，能到下一个点的概率。

那么设第一个区间叫$x_1,p_1$，第二个叫$x_2,p_2$，那么总区间可以用一个无穷级数表示：

其中$i​$是在枚举在这两个区间之间往返几次。

简单线段树维护即可，复杂度$O(n\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define data asd09123jdf02i3h
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,q;
 
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
 
struct segment_tree {
    struct data {lf x,p;}t[maxn];
 
    data merge(data a,data b) {
        data c;
        c.x=a.x*b.x/(1-(1-b.x)*a.p);
        c.p=b.p+(1-b.p)*a.p*b.x/(1-(1-b.x)*a.p);
        return c;
    }
 
    void modify(int p,int l,int r,int x,lf v) {
        if(l==r) return t[p].x=t[p].p=v,void();
        if(x<=mid) modify(ls,l,mid,x,v);
        else modify(rs,mid+1,r,x,v);
        t[p]=merge(t[ls],t[rs]);
    }
 
    data query(int p,int l,int r,int x,int y) {
        if(x<=l&&r<=y) return t[p];
        if(y<=mid) return query(ls,l,mid,x,y);
        else if(x>mid) return query(rs,mid+1,r,x,y);
        else return merge(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y));
    }
}T;
 
int main() {
    read(n),read(q);
    for(int i=1,a,b;i<=n;i++) read(a),read(b),T.modify(1,1,n,i,1.0*a/b);
    while(q--) {
        int op,l,r,x;read(op);
        if(op==1) read(x),read(l),read(r),T.modify(1,1,n,x,1.0*l/r);
        else read(l),read(r),printf("%.5lf\n",T.query(1,1,n,l,r).x);
    }
    return 0;
}