← 返回题目列表

Codeforces · 431/E

E. 化学实验

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

有一天,格里沙和戴安娜这两个学生发现自己来到了大学化学实验室。在实验室里,学生们找到了n支装有汞的试管,编号从1到n,并决定进行一个实验。

该实验由 q 个步骤组成。在每个步骤中,都会发生以下操作之一:

1. Diana 倒出 pi 号试管中的所有内容物,然后倒出恰好 xi 升水银。
2. 让我们考虑一下向管子中添加 vi 升水的所有方法;对于每种方式,让我们计算管中液体(水和汞)的体积,其中水具有最大液体量;最后让我们找到计数的最大值中的最小值。这就是学生想要数的数字。此时,学生们实际上并没有倒水银。他们在不改变试管内容物的情况下进行计算。

不幸的是,计算结果太复杂了,学生们请求你帮助他们。帮助他们进行所描述的实验。

输入

第一行包含两个整数 n 和 q (1 ≤ n, q ≤ 105) — 管数和实验步骤数。下一行包含 n 个空格分隔的整数:h1, h2, ..., hn (0 ≤ hi ≤ 109),其中 hi 是实验开始时第 i 管中汞的体积。

接下来的 q 行包含以下格式的游戏动作:

- 形式为“1 pi xi”的行表示第一种类型的动作 (1 ≤ pi ≤ n; 0 ≤ xi ≤ 109)。
- 形式“2 vi”的行表示第二类型的动作(1 ≤ vi ≤ 1015)。

保证至少有一个第二类型的动作。保证描述实验的所有数字都是整数。

输出

对于第二种类型的每个操作,打印计算值。如果答案的相对误差或绝对误差不超过 10 - 4,则认为答案是正确的。

示例

输入 #1

3 3
1 2 0
2 2
1 2 1
2 3

输出 #1

1.50000
1.66667

输入 #2

4 5
1 3 0 1
2 3
2 1
1 3 2
2 3
2 4

输出 #2

1.66667
1.00000
2.33333
2.66667