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

内存限制:1024 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: fizzydavid

题目描述

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可以正常运行。

样例

样例输入 1

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

样例输出 1

2.00000000
2.00000000
4.00000000
5.00000000
5.00000000
2.66666667
2.66666667 2.66666667 2.66666667 5.00000000 5.00000000

样例输入 2

5 2
6.62 5.02 1.49 4.35 4.01
7.83 7.10 5.90 7.93
1 3 2.91
1 4 2.17

样例输出 2

6.62000000 5.02000000 3.28333333 3.28333333 3.28333333

数据范围与提示

在这题中,我们使用一个理想模型。即我们假设水的体积不变,并且忽视水的表面张力、摩擦力等。你可以认为钻孔之后的水位变化是符合生活常识的。你可以认为,对于两个相邻的水位 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 分):无特殊限制。