CF431E Chemistry Experiment

一天，Grisha 和 Diana 两名学生来到大学化学实验室。在实验室里，他们发现了 $n$ 支编号为 $1$ 到 $n$ 的汞试管，并决定进行一次实验。 该实验包含 $q$ 个步骤。每一步都会发生以下两种操作之一： 1. Diana 倒空第 $p_{i}$ 支试管的所有内容，再往其中倒入恰好 $x_{i}$ 升的汞。 2. 设法将 $v_{i}$ 升水分配进这些试管；对于每一种分配方案，计算含水试管中的液体（汞和水）的最大体积；最后，找出所有方案里这些最大值的最小值。这个最小值就是学生们想要计算的答案。需要注意的是，他们不会真的进行加水操作，只是在计算过程中模拟这一操作，不会改变试管中汞的实际含量。 遗憾的是，这些计算太复杂了，学生们请求你帮助他们完成实验过程的模拟。请帮助他们计算上述答案。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^{5}$），分别表示试管数量和实验操作步骤数。 第二行包含 $n$ 个用空格分隔的整数 $h_{1}, h_{2}, ..., h_{n}$（$0 \leq h_{i} \leq 10^{9}$），其中 $h_{i}$ 表示实验开始时第 $i$ 支试管中的汞量。 接下来的 $q$ 行，每行表示一次操作，格式如下： - 形如 "$1$ $p_{i}$ $x_{i}$" 的一行表示第一种操作（$1 \leq p_{i} \leq n$；$0 \leq x_{i} \leq 10^{9}$）。 - 形如 "$2$ $v_{i}$" 的一行表示第二种操作（$1 \leq v_{i} \leq 10^{15}$）。 保证至少有一次第二种操作。保证所有描述实验的数据均为整数。

对于每次第二种操作，输出一行计算得出的答案。如果你的输出与标准答案的相对或绝对误差不超过 $10^{-4}$，则视为正确。

由 ChatGPT 5 翻译