CF712E Memory and Casinos

有 $n$ 个赌场排成一排。如果 Memory 在第 $i$ 个赌场赌博，他有概率 $p_i$ 赢并前往右侧的赌场（$i+1$），或者如果 $i=n$，则离开赌场；有概率 $1-p_i$ 输并前往左侧的赌场（$i-1$），或者如果 $i=1$，也直接离开赌场。 我们称 Memory 在区间 $i...\ j$ 上“支配”，当且仅当他完成一次如下的游走： - 从第 $i$ 个赌场出发； - 在 $i$ 号赌场内从未输过； - 最后以在第 $j$ 个赌场赢钱结束游走。 注意，Memory 可以走到第 $1$ 号赌场左侧或者第 $n$ 号赌场右侧，这都被认为是完成了过程。 现在，Memory 有一些请求，两种类型： - $1\ i\ a\ b$：将 $p_i$ 设为 $\frac{a}{b}$。 - $2\ l\ r$：输出 Memory 在区间 $l...\ r$ 上支配的概率，即他从赌场 $l$ 出发，最终第一次离开区间 $l...\ r$ 时，正好是在 $r$ 赢出去的概率。 保证任意时刻，$p$ 都是个不下降的序列，即对所有 $1 \leq i \leq n-1$，都有 $p_i \leq p_{i+1}$。 请你帮助 Memory 回答所有请求！

第一行输入两个整数 $n$ 和 $q$（$1 \leq n, q \leq 100000$），表示赌场数量和请求数量。 接下来 $n$ 行，每行包含整数 $a_i$ 和 $b_i$（$1 \leq a_i < b_i \leq 10^9$），表示第 $i$ 个赌场的概率 $p_i = \frac{a_i}{b_i}$。 接下来 $q$ 行，每行给出一种请求，格式如下之一（$1 \leq a < b \leq 10^9$，$1 \leq i \leq n$，$1 \leq l \leq r \leq n$）： - $1\ i\ a\ b$ - $2\ l\ r$ 保证至少有一个 $2$ 型请求，输出不为空；且任意时刻，$p$ 是不下降的序列。

对于每个类型为 $2$ 的请求，输出 Memory 在对应区间的“支配”概率。每行输出一个实数，绝对误差不超过 $10^{-4}$。 即，假设某一行你的输出为 $a$，标准答案为 $b$，当且仅当 $|a-b| \leq 10^{-4}$ 时，该答案才会被认定为正确。

由 ChatGPT 5 翻译