CF712E Memory and Casinos 题解

题意：

现有一排 $n$ 个赌场。

cxy 在第 $i$ 个赌场时有 $p_i$ 的几率获胜并移动到第 $i+1$ 个赌场，如果 $i=n$ 则 cxy 会离开赌场；

同时有 $1-p_i$的概率失败并移动到第 $i-1$ 个赌场，如果$i=1$ 则 cxy 会离开赌场。

定义 cxy “掌控”一段区间 $[i,j]$ 当且仅当 cxy 完成以下过程：

cxy 从 $i$ 号赌场出发；

cxy 从未在 $i$ 号赌场失败；

cxy 某一次在 $j$ 号赌场获胜并离开。

现在有 $q$ 次操作，操作有以下两种：

$1\ i\ a\ b$：令 $p_i = \frac{a}{b}$；

$2\ l\ r$：询问 cxy “掌控”区间 $[l,r]$ 的概率。

保证在任意时刻 $p_i$ 构成的序列是单调不降的。

关键词：线段树、等比数列求和、概率、DP（思想）

设 $f(l,r)$ 表示在 $l$ ，不到达 $l-1$ ，并从 $r$ 走出的概率.

为了方便转移，设 $g(l,r)$ 表示在 $r$ ，不到达 $r+1$ ，并从 $l$ 走出的概率

考虑线段树上怎么合并两个区间的答案

不妨设左侧为 $(f_1,g_1)$ ，右侧为 $(f_2,g_2)$ ，最后的答案为 $(f,g)$

首先考虑 $f$

$f=f_1f_2\sum_{r=0}^{+\infty}\left[(1-f_2)(1-g_1)\right]^r$

这个看上去复杂，其实不然。

$r=0$ ，就是直接一遍过

$r=1$ ，就是中间转了一圈再过

$r=k$ ，就是中间转了 $k$ 圈再过

然后这个东西其实就是等比数列求和

根据公式 $S(n) = \dfrac{a_1(1-q^n)}{1-q},q\ne 1$

$f = \dfrac{f_1f_2\left\{1-\lim\limits_{r \to +\infty}\left[(1-f_2)(1-g_1)\right]^{r}\right\}}{1-(1-f_2)(1-g_1)} = \dfrac{f_1f_2}{1-(1-f_2)(1-g_1)}$

同理，也能推出

$\begin{aligned} g&=g_1g_2\sum_{r=0}^{+\infty}\left[ (1-g_1)(1-f_2)\right]^r \\&=\dfrac{g_1g_2}{1-(1-f_2)(1-g_1)} \end{aligned}$

然后我们就能 $O(1)$ 合并两个子区间啦！

时间复杂度 $O( (n + q)\log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define DEBUG (cout << "1145141919810...")
#define N ((int)(1e5+15))
typedef pair<double,double> P;
#define F first
#define S second

int n,Q;
double p[N];
struct node{double f,g;} tr[N*4];
#define ls(at) (at << 1)
#define rs(at) (at << 1 | 1)
void push_up(int at)
{
    double f1 = tr[ls(at)].f, f2=tr[rs(at)].f;
    double g1 = tr[ls(at)].g, g2=tr[rs(at)].g;
    tr[at].f = f1 * f2 / (1 - (1-f2) * (1-g1));
    tr[at].g = g1 * g2 / (1 - (1-f2) * (1-g1));
}
void build(int l,int r,int at)
{
    if(l==r) return tr[at]={p[l],1-p[l]},void(0);
    int mid = (l+r) >> 1;
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
    push_up(at);
}
void modify(int x,int l,int r,double k,int at)
{
    if(l==r) return tr[at]={k,1-k},void(0);
    int mid = (l+r) >> 1;
    if(x <= mid) modify(x,l,mid,k,ls(at));
    else modify(x,mid+1,r,k,rs(at));
    push_up(at);
}
P query(int nl,int nr,int l,int r,int at)
{
    if(nl <= l && r <= nr) return {tr[at].f, tr[at].g};
    int mid = (l+r) >> 1;
    if(nr <= mid) return query(nl,nr,l,mid,ls(at));
    else if(nl > mid) return query(nl,nr,mid+1,r,rs(at));
    P res1=query(nl,nr,l,mid,ls(at)), res2=query(nl,nr,mid+1,r,rs(at));
    return {res1.F * res2.F / (1 - (1 - res2.F) * (1 - res1.S)),
            res1.S * res2.S / (1 - (1 - res2.F) * (1 - res1.S))};
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(10);
    cin >> n >> Q;
    for(int i=1,x,y; i<=n; i++)
        cin >> x >> y, p[i] = 1.0 * x / y;
    build(1,n,1);
    for(int op,x,a,b; Q--;)
    {
        cin >> op;
        if(op==1)
        {
            cin >> x >> a >> b;
            modify(x,1,n,1.0*a/b,1);
        }else
        {
            cin >> a >> b;
            cout << query(a,b,1,n,1).F << '\n';
        }
    }
    return 0;
}