Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:256 MB
统计

米尔科最近安装了一个新的屏幕保护程序。如果他离开键盘五分钟,屏幕显示一个图片的水族馆与动画。屏幕保护程序已定制的形状并可以设置水族箱底部和水位。
我们可以把水族馆看成是一个二维平面N-1列宽,N是正整数。左边墙的X坐标是0,右边墙的X坐标是N-1。每一个对应的整数X,都用来描述一列水族馆的底部,我们用0到N-1来描述。我们用Hi来描述X坐标为i的这一处底部的高度。所以在任意两个相邻底部的X坐标为i和i+1,它们在二维平面上用(i,Hi)和(i+1,Hi+1)来描述。
如果水位设置成h,水将填满所有y=h到底部的空间。如果一部分底部高于h,则它形成一个小岛,不会被灌水。
对于每一个高,我们要算出被灌水的面积。
输入:
第一行两个正整数。N (3 ≤ N ≤ 100 000, 底部的宽度。)和 M (1 ≤ M ≤ 100 000,问题的个数).
接下来一行N个非负数,Hi (0 ≤ Hi ≤ 1000), 表示每一处底部的最初高度。
接下来M行,每行一个问题。
格式如下:
Q h,表示询问在当前底部情况下,水位设置成h (0 ≤ h ≤ 1000),有多少面积被水灌满。
U i h 表示把X坐标为ii (0 ≤ i ≤ N - 1)的底部改成h (0 ≤ h ≤1000)即让Hi=h.
输出:
对于每一个Q,回答一个值,表示灌水的面积,保留3位小数。与标准答案的误差最多不差过0.001。
样例:

input 
3 2 
20 20 20 
Q 20 
Q 30 
output 
0.000 
20.000
input 
3 5 
0 2 0 
Q 2 
U 1 1 
Q 1 
U 1 10 
Q 5 
output 
2.000 
1.000 
2.500 
input 
7 7 
0 2 1 3 2 1 0 
Q 1 
Q 2 
Q 3 
U 3 0 
Q 1 
Q 2 
Q 3 
output 
0.750 
3.750 
9.000 
1.500 
6.000 
12.000

对于样例3如下图:
左边的图形表示最初的底部,右边表示改后的底部。它们的水位都设置成2,即回答Q 2 的效果图。第一个图的灌水面积3.75.第二个图是6.