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;
}