Description

Mirko 最近安装了一个新的屏保。如果他离开键盘五分钟，屏幕上就会显示一幅有动画鱼的水族箱图片。这个屏保可以自定义（虚拟的、带沙底的）水族箱底部的形状以及水位高度。

这个水族箱可以用二维直角坐标系来表示，宽度为 $N-1$ 列，其中 $N$ 是正整数。水族箱的左侧壁的 $x$ 坐标为 $0$，右侧壁的 $x$ 坐标为 $N-1$。水族箱底部每一个整数 $x$ 坐标（记为 $i$，$0 \leq i \leq N-1$）都有一个可以单独调整的高度 $H_i$。对于任意相邻的整数坐标 $i$ 和 $i+1$，底部由 $(i, H_i)$ 到 $(i+1, H_{i+1})$ 的线段描述。

如果水位设为 $h$，水会填满 $y = h$ 与水族箱底部之间的区域。若某些底部高于水位 $h$，则这些部分会形成“岛屿”，不会被水淹没。

对于不同的水族箱底部形状，Mirko 想知道屏幕上被水覆盖的总面积。请帮 Mirko 解答这个问题（除了 42 以外的答案）。

Input Format

第一行输入两个正整数 $N$（$3 \leq N \leq 100\,000$，底部长度）和 $M$（$1 \leq M \leq 100\,000$，询问数量）。

第二行输入 $N$ 个非负整数 $H_i$（$0 \leq H_i \leq 1000$），表示初始底部的高度。

接下来的 $M$ 行，每行一个询问，格式如下两种之一：

• Q $h$ —— 若水位为 $h$（$0 \leq h \leq 1000$），在当前底部形状下，被水覆盖的总面积是多少？
• U $i$ $h$ —— Mirko 决定将 $x$ 坐标为 $i$（$0 \leq i \leq N-1$）处的底部高度改为 $h$（$0 \leq h \leq 1000$），即 $H_i = h$。

Output Format

对于每个 Q 类型的询问，输出一行，表示所求面积，四舍五入保留三位小数。答案与官方标准答案的误差不超过 $0.001$ 即可。

3 2
20 20 20
Q 20
Q 30

0.000
20.000 

3 5
0 2 0
Q 2
U 1 1
Q 1
U 1 10
Q 5

2.000
1.000
2.500

7 7
0 2 1 3 2 1 0
Q 1
Q 2
Q 3
U 3 0
Q 1
Q 2
Q 3 

0.750
3.750
9.000
1.500
6.000
12.000 

Hint

第三个样例的说明：下图左侧是修改前，右侧是 U 类型操作后，水位 $h=2$（Q 2 询问）的情形。左图淹没面积为 $3.75$，右图为 $6$。

翻译由 ChatGPT-4.1 完成。