E. Memory and Casinos

有 #cf_span[n] 个赌场排成一行。如果 Memory 在赌场 #cf_span[i] 玩，他有概率 #cf_span[pi] 获胜并移动到右边的赌场 (#cf_span[i + 1])，或离开该行（如果 #cf_span[i = n]）；也有概率 #cf_span[1 - pi] 失败并移动到左边的赌场 (#cf_span[i - 1])，或同样离开该行（如果 #cf_span[i = 1]）。 我们说 Memory 在区间 #cf_span[i... j] 上 _支配_，如果他完成了一次行走，使得 注意，Memory 仍可以走到第 #cf_span[1] 个赌场的左侧或第 #cf_span[n] 个赌场的右侧，并且总是会结束该过程。 现在 Memory 有一些请求，形式如下： 保证在任何时刻，#cf_span[p] 是一个 *非递减序列*，即对所有 #cf_span[i] 从 #cf_span[1] 到 #cf_span[n - 1]，都有 #cf_span[pi ≤ pi + 1]。 请帮助 Memory 回答所有请求！ 输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n, q ≤ 100 000]），分别表示赌场数量和请求数量。 接下来的 #cf_span[n] 行每行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai < bi ≤ 109]），表示在赌场 #cf_span[i] 获胜的概率 #cf_span[pi]。 接下来的 #cf_span[q] 行每行包含上述类型之一的查询（#cf_span[1 ≤ a < b ≤ 109]，#cf_span[1 ≤ i ≤ n]，#cf_span[1 ≤ l ≤ r ≤ n]）。 保证至少存在一个类型为 #cf_span[2] 的查询，即输出非空。此外，保证 #cf_span[p] 始终构成一个非递减序列。 对每个类型为 #cf_span[2] 的请求，输出一个实数——该区间上男孩“支配”的概率。你的答案若绝对误差不超过 #cf_span[10 - 4]，则被视为正确。 具体而言：假设你的一个答案是 #cf_span[a]，判题标准答案是 #cf_span[b]，当 #cf_span[|a - b| ≤ 10 - 4] 时，判题程序将认为你的答案正确。 ## Input 输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n, q ≤ 100 000]），分别表示赌场数量和请求数量。接下来的 #cf_span[n] 行每行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai < bi ≤ 109]），表示在赌场 #cf_span[i] 获胜的概率 #cf_span[pi]。接下来的 #cf_span[q] 行每行包含上述类型之一的查询（#cf_span[1 ≤ a < b ≤ 109]，#cf_span[1 ≤ i ≤ n]，#cf_span[1 ≤ l ≤ r ≤ n]）。保证至少存在一个类型为 #cf_span[2] 的查询，即输出非空。此外，保证 #cf_span[p] 始终构成一个非递减序列。 ## Output 对每个类型为 #cf_span[2] 的请求，输出一个实数——该区间上男孩“支配”的概率。你的答案若绝对误差不超过 #cf_span[10 - 4]，则被视为正确。具体而言：假设你的一个答案是 #cf_span[a]，判题标准答案是 #cf_span[b]，当 #cf_span[|a - b| ≤ 10 - 4] 时，判题程序将认为你的答案正确。 [samples]

Let $ n $ be the number of casinos, indexed $ 1 $ to $ n $. For each casino $ i $, define the win probability as $ p_i = \frac{a_i}{b_i} $, where $ 1 \leq a_i < b_i \leq 10^9 $, and $ p_i \leq p_{i+1} $ for all $ 1 \leq i < n $. Define a random walk on the integers $ \mathbb{Z} $, starting at position $ x \in [l, r] $, with transition rules: - From state $ i \in \{2, \dots, n-1\} $: move to $ i+1 $ with probability $ p_i $, to $ i-1 $ with probability $ 1 - p_i $. - From state $ 1 $: move to $ 0 $ (left exit) with probability $ 1 - p_1 $, to $ 2 $ with probability $ p_1 $. - From state $ n $: move to $ n+1 $ (right exit) with probability $ p_n $, to $ n-1 $ with probability $ 1 - p_n $. Define the event "dominates on $ [l, r] $" as: starting at $ l $, the walk reaches $ r+1 $ before reaching $ l-1 $. Let $ f(l, r) $ denote the probability that, starting at $ l $, the walk reaches $ r+1 $ before $ l-1 $. Then, for each query of type 2 (interval $ [l, r] $), output $ f(l, r) $. For each query of type 1 (update casino $ i $ with new $ a_i, b_i $), update $ p_i \leftarrow \frac{a_i}{b_i} $, maintaining the non-decreasing property. Objective: Answer each type-2 query with $ f(l, r) $, computed via the standard gambler’s ruin formula for non-uniform probabilities on a line segment with absorbing barriers at $ l-1 $ and $ r+1 $, given $ p_i $ for $ i \in [l, r] $. --- **Formal Definition of $ f(l, r) $:** Let $ p_i \in [0,1] $ for $ i = l, l+1, \dots, r $, with $ p_i \leq p_{i+1} $. Define: $$ f(l, r) = \left(1 + \sum_{k=l}^{r} \prod_{j=l}^{k} \frac{1 - p_j}{p_j} \right)^{-1} $$ This is the probability of reaching $ r+1 $ before $ l-1 $, starting from $ l $, in a birth-death chain with state-dependent transition probabilities $ p_i $. --- **Given:** - $ n, q \in \mathbb{N} $, $ 1 \leq n, q \leq 10^5 $ - Initial $ a_i, b_i $ for $ i = 1 $ to $ n $, defining $ p_i = \frac{a_i}{b_i} $ - Updates: type 1: set $ a_i, b_i $ for some $ i $, update $ p_i $ - Queries: type 2: compute $ f(l, r) = \left(1 + \sum_{k=l}^{r} \prod_{j=l}^{k} \frac{1 - p_j}{p_j} \right)^{-1} $ **Output:** For each type-2 query, output $ f(l, r) $ with absolute error $ \leq 10^{-4} $.