3082 「2019 集训队互测 Day 5」小水题

CauchySheep 出了一道小水题。 有 $n$ 个底面积相同的水槽排成一排，相邻两个水槽共用一个隔板，第 $i$ 个水槽与第 $i+1$ 个水槽之间的隔板高度为 $b_i$。最左边与最右边的隔板高度可以视为无限大。初始时所有水槽是静止的，第 $i$ 个水槽初始水位是 $a_i$。你需要维护以下两种操作： - 给定 $x$ 和 $h$，在第 $x$ 个水槽和第 $x+1$ 个水槽之间的隔板的高度 $h$ 处钻一个小孔。这之后一些水槽的水位会发生变化，你应该一直等到这些水槽恢复静止。 - 给定 $x$，询问此时第 $x$ 个水槽的水位。 请你完成这道充满着水的小水题吧！

从标准输入读入数据。

第一行两个整数 $n, q$，分别表示水槽数和操作数。

第二行 $n$ 个由空格隔开的实数 $a_i$，表示初始水位。

第三行 $n-1$ 个由空格隔开的实数 $b_i$，表示初始隔板高度。

接下来 $q$ 行每行描述一个操作：

• 1 x h 表示第一种操作，保证 $1 \le x \lt n$。注意 $h$ 是实数。
• 2 x 表示第二种操作，保证 $1 \le x \le n$。

输入中出现的所有实数最多有七位小数。

输出到标准输出中。

对于第二种操作，每一行输出答案。

最后一行输出 $n$ 个空格隔开的实数，表示操作结束后的每个水槽的水位。

绝对误差在 $10^{-7}$ 内即可接受。

注意你应该保证你的输出中只有实数（或整数），否则我们不能保证spj可以正常运行。

在这题中，我们使用一个理想模型。即我们假设水的体积不变，并且忽视水的表面张力、摩擦力等。你可以认为钻孔之后的水位变化是符合生活常识的。你可以认为，对于两个相邻的水位 $a_i, a_{i+1}$，以及它们之间隔板存在一个高度为 $h$ 的小孔（或初始隔板高度为 $h$ ），如果有 $a_i \gt h, a_i \gt a_{i+1}$，那么将会有水从 $i$ 流向 $i+1$。对称地，如果有 $a_{i+1} \gt h, a_{i+1} \gt a_i$，那么将会有水从 $i+1$ 流向 $i$。水从 $x$ 流向 $y$ 是指 $a_x$ 不断减少，$a_y$ 不断增加，并且保持它们的和不变。

出题人友情提醒： 请妥善处理浮点数运算造成的精度误差。

对于所有测试数据，$1 \le n, q \le 100000$，$0 \le a_i, h \le 100$，对于 $1 \le i \lt n$，有 $b_i \ge \max(a_i, a_{i+1})$。输入中出现的所有实数最多有七位小数。

• 子任务 $1$（$1$ 分）：$1 \le n, q \le 10$；
• 子任务 $2$（$10$ 分）：$1 \le n, q \le 300$；
• 子任务 $3$（$10$ 分）：$1 \le n, q \le 2000$，对于 $i\gt 1$，满足 $a_i = 0$；
• 子任务 $4$（$10$ 分）：$1 \le n, q \le 2000$；
• 子任务 $5$（$30$ 分）：对于 $i>1$，满足 $a_i = 0$；
• 子任务 $6$（$39$ 分）：无特殊限制。