#1972. 小水题

    ID: 1972 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest315来源:qoj.ac数据:公开样例模拟排序

小水题

小水题

题目描述

标题: 小水题 - Problem - QOJ.ac

#8466. 小水题

Statistics

The problem was used in the following contests:

CauchySheep 出了一道小水题。

有 n 个底面积相同的水槽排成一排,相邻两个水槽共用一个隔板,第 i 个水槽与第 i+1 个水槽之间的隔板高度为 bi。最左边与最右边的隔板高度可以视为无限大。初始时所有水槽是静止的,第 i 个水槽初始水位是 ai。你需要维护以下两种操作:

  • 给定 x 和 h,在第 x 个水槽和第 x+1 个水槽之间的隔板的高度 h 处钻一个小孔。这之后一些水槽的水位会发生变化,你应该一直等到这些水槽恢复静止。
  • 给定 x,询问此时第 x 个水槽的水位。

请你完成这道充满着水的小水题吧!

输入格式

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

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

第三行 n−1 个由空格隔开的实数 bi,表示初始隔板高度。

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

  • 1 x h 表示第一种操作,保证 1≤x<n。注意 h 是实数。
  • 2 x 表示第二种操作,保证 1≤x≤n。

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

输出格式

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

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

绝对误差在 10−7 内即可接受。

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

样例数据

样例输入

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

样例输出

2.00000000
2.00000000
4.00000000
5.00000000
5.00000000
2.66666667
2.66666667 2.66666667 2.66666667 5.00000000 5.00000000

样例输入

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

样例输出

6.62000000 5.02000000 3.28333333 3.28333333 3.28333333

子任务

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

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

对于所有测试数据,1≤n,q≤100000,0≤ai,h≤100,对于 1≤i<n,有 bi≥max(ai,ai+1)。输入中出现的所有实数最多有七位小数。

  • 子任务 1(1 分):1≤n,q≤10;
  • 子任务 2(10 分):1≤n,q≤300;
  • 子任务 3(10 分):1≤n,q≤2000,对于 i>1,满足 ai=0;
  • 子任务 4(10 分):1≤n,q≤2000;
  • 子任务 5(30 分):对于 i>1,满足 ai=0;
  • 子任务 6(39 分):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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
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
6.62000000 5.02000000 3.28333333 3.28333333 3.28333333