H-Mountain View_2026牛客五一集训派对day5

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

You enjoy the mountain view, especially on a rainy day.

For a positive integer sequence $b_1,b_2,\cdots, b_k(k \geq 2)$ , you define its beauty as following:

Suppose there is a broken line connecting $(1, b_1), (2, b_2), \cdots, (k, b_k)$ one by one on the Cartesian plane, representing a mountain's outline. To the immediate right of $(k, b_k)$ is a vertical cliff whose height can be assumed infinite (but to the left of $(1, b_1)$ there isn't). Small ponds form on rainy days, and the beauty is the maximum ponding area on this 2D graph.

Now you have an integer sequence $a_1, a_2, \cdots, a_n$ . Support two operations:

`1 x y` — Set $a_x$ to $y$ .
`2 l r` — Print the beauty of $a_l, a_{l+1}, \cdots, a_r$ .

输入描述:

The first line contains two integers $n$ and $q$ ( $2 \leq n \leq 10^5$ , $1 \leq q \leq 10^5$ ).

The second line contains $n$ integers: the initial values of $a_1, a_2, \cdots, a_n$ ( $1 \leq a_i \leq 10^9$ ).

The next $q$ lines each contain three integers, representing the operations. It is guaranteed that $1 \leq x \leq n$ , $1\leq y \leq 10^9$ , $1 \leq l < r \leq n$ .

输出描述:

Print the answer for each query. The answer may not be an integer, so your output will be considered correct if its absolute or relative error does not exceed .

示例1

输入

复制

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

输出

复制

7.791666666667
0.000000000000
4.750000000000
5.416666666667

说明

The blue area of the image in the statement demonstrates the first query of the first sample.