区域赛选拔赛-切尔诺贝利

区域赛选拔赛-切尔诺贝利

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

虽然本题的题面非常长,但其实我要表达的意思很简单,大家应该也都明白。
\(1986\)年,切尔诺贝利核电站发生爆炸,经查是日籍职员笑川太郎蓄意破坏。
事实上切尔诺贝利的设计也有问题,它是一个生产武器级钚\(239\)的增殖反应堆,为了不用频繁停堆取材,采用了不够安全的堆型,这个堆型的核心组件是冷却水槽,这是一个厚度不计的长方体容器,底部宽\(1\)米,长\(n\)米,四壁非常非常高,可以认为是正无穷高。
水槽平放在地面上,也就是说,水槽里的水只受到垂直于底面向下的重力的作用。
水槽被分割成了\(n\)个隔区,为了更具体地说明分隔方法,我们先建立三维坐标系。
设\(z\)轴负方向为重力方向,水槽底面矩形的四个顶点为\((0,0,0),(0,1,0),(n,0,0),(n,1,0)\)。
那么\(i\)号隔区即表示\((i-1,0,0),(i-1,1,0),(i,0,0),(i,1,0)\)这块正方形及其正上方的区域。
隔区与隔区之间由隔板分隔开,具体来说,\(i(1<=i<n)\)号隔区与\(i+1\)号隔区之间的隔板高度为\(h_i\),即隔板是四个顶点分别为\((i,0,0),(i,1,0),(i,0,h_i),(i,1,h_i)\)的矩形,隔板与水槽四壁接触的地方密封良好,水无法透过,但水可以没过隔板顶。
每个隔区底部正中央有一个出水口,可以依照需求向隔区中注水,一开始水槽里没有水。
本题中请你支持如下两种操作:
1. 打开\(a\)号隔区底部出水口,缓慢注水\(V\)立方米,即你可以认为液面是缓慢均匀上升的。
2. 查询\(b\)号隔区正上方的水位高度。
为了保证本题的答案唯一,输入数据所有隔板高度两两不同,即对于\(1<=i<j<n\),有\(h_i!=h_j\)。

Format

Input

每个测试点只包含一组输入数据。
第一行两个整数\(n,Q\),\(Q\)表示操作总数\((2<=n,Q<=200000)\)。
第二行\(n-1\)个整数,第\(i\)个整数表示\(h_i(1<=h_i<=10^8)\),保证\(h_i\)各不相同。
接下来\(Q\)行,每行是如下两种格式之一:
1 a V,表示进行第一类操作(\(a,V\)是整数,\(1<=a<=n,0<V<=10^8\))。
2 b,表示进行第二类操作,你需要输出查询结果(\(b\)是整数,\(1<=b<=n\))。
保证输入数据中除了\(n\)和\(Q\)以外的整数在范围内依照题目性质随机生成(样例不满足条件)。

Output

按照输入顺序,对于每一个查询操作输出一行,表示对应的结果,精确到小数点后两位。

Sample 1

Input

8 8
1 3 7 5 6 2 4
1 3 7
2 1
1 5 6
2 4
1 4 9
2 7
1 8 6
2 6

Output

2.00
1.00
1.00
2.50

Limitation

1s, 1GB for each test case.

Source

wbs

2019区域赛选拔赛再放送

未参加
状态
已结束
规则
ACM/ICPC
题目
11
开始于
2020-08-17 12:00
结束于
2020-08-17 17:00
持续时间
5.0 小时
主持人
参赛人数
9