← 返回题目列表

Codeforces · 712/E

E. 内存和赌场

中文机器翻译题面 查看原题

有 n 个赌场排成一排。如果 Memory 在赌场 i 玩游戏,他有概率 pi 获胜并移至右侧赌场 (i + 1) 或退出该行(如果 i = n),并且有概率 1 - pi 输并移至左侧赌场 (i - 1) 或退出该行(如果 i = 1)。

如果他完成一次步行,我们就说记忆在区间 i... j 上占主导地位,

- 他从赌场 i 开始。
- 他在赌场从来没有输过。
- 他在赌场 j 中获胜,结束了他的步行。

请注意,内存仍然可以走在第 1 个赌场的左侧和赌场 n 的右侧,并且始终会完成该过程。

现在内存有一些请求,采用以下形式之一:

- 1 i a b:设置$$p_i = \frac{a}{b}$$。
- 2 l r:打印 Memory 在区间 l...r 上占主导地位的概率,即计算 Memory 在赌场 r 获胜后首先离开分段 l...r 的概率,如果她从赌场 l 开始。

保证在任何时刻 p 都是非递减序列,即对于从 1 到 n - 1 的所有 i,pi ≤ pi + 1。

请帮助记忆满足他的所有请求!

输入

输入的第一行包含两个整数 n 和 q(1 ≤ n, q ≤ 100 000), — 分别是赌场数量和请求数量。

接下来的 n 行每行包含整数 ai 和 bi (1 ≤ ai < bi ≤ 109)  — $$\frac{a_{i}}{b_{i}}$$ 是在赌场 i 获胜的概率 pi。

接下来的 q 行每行包含上述指定类型之一的查询(1 ≤ a < b ≤ 109、1 ≤ i ≤ n、1 ≤ l ≤ r ≤ n)。

保证至少有一个类型 2 的查询,即输出非空。另外,保证p始终形成非递减序列。

输出

为类型 2 的每个请求打印一个实数 - 男孩在该时间间隔内“占主导地位”的概率。如果绝对误差不超过 10 - 4,您的答案将被视为正确。

即:假设你的答案之一是a,陪审团相应的答案是b。如果|a - b|,检查程序将认为您的答案正确。 ≤ 10 - 4。

示例

输入 #1

3 13
1 3
1 2
2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3
1 2 2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3

输出 #1

0.3333333333
0.2000000000
0.1666666667
0.5000000000
0.4000000000
0.6666666667
0.3333333333
0.2500000000
0.2222222222
0.6666666667
0.5714285714
0.6666666667