CF712E [Memort and Casinos]

题意

每次询问一段区间[l,r]，求从最左边走到最右边（r+1）的概率（若走到l-1，则GG了），每个点上写有向右走的概率。支持单点修改。

思考

若只查询一次，那只要知道每个点在不走到l-1的情况下，向右移动一格的概率就行了，最后乘起来就是答案。

但我们忽略了一件事情，若从一个区间的某一点出发，从左边走出去和右边走出去的概率和为1（不可能停在中间），于是我们要设计一个状态，并能够合并，这样才有可能优化复杂度。

设 [l,r] 区间的L为从第l个点（最左边）出发，在右边走出去的概率，R为第R个点出发，在左边走出去的概率。

[L1	-->	R1]	[L2	-->	R2]
[ L	--	--	--	-->	R ]

请记住，他们每个的实际意义。因为每个点要么从左边走出去，要么从右边走出去，所（1-L1）的实际意义就是从（左边出发，不从右边走出），即（从左边出发，从左边走出去的概率）。

那么若有两个连续的区间，合并成一个新区间会有怎样的答案？设左右两个区间的答案分别为L1,R1,L2,R2，则：

L = L₁*L₂走到右边还要再走到更右边

+ L₁(1-L₂)(1-R₁)*L₂第一次向右边走失败了，再退回来再向右走

+ L₁(1-L₂)(1-R₁)(1-L₂)(1-R₁)*L₂反反复复.......

+.......

整理一下，
L = L₁L₂+L₁L₂(1-L₂)(1-R₁)+L₁L₂(1-L₂)²+.......
(1-L₂)(1-R₁)L = L₁L₂(1-L₂)(1-R₁)+L₁L₂(1-L₂)²+.......

作差，

L(1-(1-L₂)(1-R₁))=L₁L₂

L=L₁L₂/(1-(1-L₂)(1-R₁))

R也可以类似地得到，但注意它们的和不一定为1，因为是两个不同的端点。

简单地线段树维护。

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1E5+5;
 4 int n,m;
 5 double x,y,a[maxn];
 6 struct tree{int l,r;double L,R;}t[maxn*4];
 7 tree merge(tree x,tree y)
 8 {
 9     tree z;
10     z.l=x.l;z.r=y.r;
11     z.L=x.L*y.L/(1-(1-y.L)*(1-x.R));
12     z.R=x.R*y.R/(1-(1-y.L)*(1-x.R));//不要认为反一反就对了QAQ 
13     return z;
14 }
15 void build(int l,int r,int num)
16 {
17     t[num].l=l,t[num].r=r;
18     if(l==r)
19     {
20         t[num].L=a[l];
21         t[num].R=1-a[l];
22         return;
23     }
24     int mid=(l+r)>>1;
25     build(l,mid,num*2);build(mid+1,r,num*2+1);
26     t[num]=merge(t[num*2],t[num*2+1]);
27 }
28 void change(int pos,double val,int num)
29 {
30     if(t[num].l==t[num].r)
31     {
32         t[num].L=val;
33         t[num].R=1-val;
34         return;
35     }
36     int mid=(t[num].l+t[num].r)>>1;
37     if(pos<=mid)change(pos,val,num*2);
38     else change(pos,val,num*2+1);
39     t[num]=merge(t[num*2],t[num*2+1]);
40 }
41 tree ask(int L,int R,int num)
42 {
43     if(L<=t[num].l&&t[num].r<=R)return t[num];
44     int mid=(t[num].l+t[num].r)>>1;
45     if(R<=mid)return ask(L,R,num*2);
46     else if(mid<L)return ask(L,R,num*2+1);
47     else return merge(ask(L,R,num*2),ask(L,R,num*2+1));
48 }
49 int main()
50 {
51     ios::sync_with_stdio(false);
52     cin>>n>>m;
53     for(int i=1;i<=n;++i)
54     {
55         cin>>x>>y;
56         a[i]=x/y;
57     }
58     build(1,n,1);
59     while(m--)
60     {
61         int opt,d;
62         cin>>opt;
63         if(opt==1)
64         {
65             cin>>d>>x>>y;
66             change(d,x/y,1);
67         }
68         else
69         {
70             int l,r;
71             cin>>l>>r;
72             cout<<fixed<<setprecision(8)<<ask(l,r,1).L<<endl;
73         }
74     }
75     return 0;
76 }

View Code