题目链接
\(Firstly\),前言
这道题是道假的黑题
一群学弟比我先A ，我真是太弱了
我们的思路都应该是来自于这位大佬的 czpcf
自我认为他们的公式都推得很草率
所以我才决定再 写一篇
\(Secondly\),思路
定义 \(f(i,j)\) 为从赌场\(i\)出发 在赌场\(i\)赢 在赌场\(j\)赢并结束的概率
定义 \(f(j + 1,k)\) 为从赌场\(j\) ＋ 1出发 在赌场\(j\) + 1赢 在赌场\(k\)赢并结束的概率
定义 \(g(i,j)\) 与 \(f\)恰相反
那么 \(f(i,k)\) = 直接走过去的概率（这里中间也可能转了圈 但没有过\(j\)） + 在中间转了圈且走过去的概率(中间的圈过了\(j\))
直接走过去的概率 = \(f(i,j) *f(j + 1,k)\)
在中间转了圈且走过去的概率 = \(f(i,j) *f(j + 1,k)\)*\(\displaystyle\sum^{+\infty}_{p=1}w^p\)
其中\(w\)为在中间转一圈的概率
重点就是 \(w\)怎么算
\(w\) = \((1-f(j+1,k))(1-g(i,j))\)
这个式子是怎么得出的呢？
先理解\(1-f(j+1,k)\)
为从赌场\(j\) ＋ 1出发 在赌场\(j\) + 1赢 在赌场\(k\)赢并结束的概率
这里 \(1-f(j+1,k)\)
赌场\(j\) ＋ 1出发是默认的
条件只有
1:在赌场\(j\) + 1赢
2:在赌场\(k\)赢
两个中至少有一个不成立
但最后\(1,2\)造成的结果都是从右区间返回 （不管她在\([j + 1,k]\)转多少圈）
\(Additionally\),化简
\[f(i,k)\]
\[= f(i,j) *f(j + 1,k)\displaystyle\sum^{+\infty}_{p=1}w^p\]
\[= f(i,j) *f(j + 1,k)\frac{1-w^{+\infty}}{1-w}\]
\[w^{+\infty} = 0\]
\[\Rightarrow= \frac{f(i,j) *f(j + 1,k)}{1-(1-f(j+1,k))(1-g(i,j))}\]
这下就可以用线段树维护了
\(Eventually\)，\(Code\)
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= (x)&&(x) <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0,f = 1;
char a = getchar();
while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
return x * f;
}
#define fi first
#define se second
typedef double db;
const int MAXN = 100010;
db p[MAXN];
struct node
{
double g,f;
}tree[MAXN << 2];
inline void sum(db &f,db &g,db f1,db f2,db g1,db g2)
{
f = f1 * f2 / (1 - (1 - f2) * (1 - g1));
g = g1 * g2 / (1 - (1 - f2) * (1 - g1));
}
inline void BuildTree(int k,int l,int r)
{
if(l == r)
{
tree[k].f = p[l],tree[k].g = 1 - p[l];
return;
}
int mid = l + r >> 1;
BuildTree(k << 1,l,mid);
BuildTree(k << 1 | 1,mid + 1,r);
sum(tree[k].f,tree[k].g,tree[k << 1].f,tree[k << 1 | 1].f,tree[k << 1].g,tree[k << 1 | 1].g);
}
inline pair<db,db> query(int k,int l,int r,int L,int R)
{
if(L <= l&&r <= R) return make_pair(tree[k].f,tree[k].g);
int mid = l + r >> 1;
pair<db,db> k1,k2;k1.fi = k2.fi = k1.se = k2.se = 1;
if(L <= mid) k1 = query(k << 1,l,mid,L,R);
if(mid < R) k2 = query(k << 1 | 1,mid + 1,r,L,R);
db T1,T2;
sum(T1,T2,k1.fi,k2.fi,k1.se,k2.se);
return make_pair(T1,T2);
}
inline void update(int k,int l,int r,int pos,db x)
{
if(l == r)
{
tree[k].f = x,tree[k].g = 1 - x;
return;
}
int mid = l + r >> 1;
if(pos <= mid) update(k << 1,l,mid,pos,x);
else update(k << 1 | 1,mid + 1,r,pos,x);
sum(tree[k].f,tree[k].g,tree[k << 1].f,tree[k << 1 | 1].f,tree[k << 1].g,tree[k << 1 | 1].g);
}
int main()
{
int n = Read(1),q = Read(1);
for(reg i = 1;i <= n;i++)
{
int a = Read(1),b = Read(1);
p[i] = (db)a / b;
}
BuildTree(1,1,n);
while(q--)
{
int sit = Read(1);
if(sit & 1)
{
int pos = Read(1),a = Read(1),b = Read(1);
update(1,1,n,pos,((db)a / b));
} else {
int l = Read(1),r = Read(1);
cout << query(1,1,n,l,r).fi << endl;
}
}
return 0;
}