CF1696G Fishingprince Plays With Array Again

Suppose you are given a 1-indexed sequence $ a $ of non-negative integers, whose length is $ n $ , and two integers $ x $ , $ y $ . In consecutive $ t $ seconds ( $ t $ can be any positive real number), you can do one of the following operations: - Select $ 1\le i

The first line of input contains two integers $ n $ and $ q $ ( $ 2\le n\le 2\cdot 10^5 $ , $ 1\le q\le 2\cdot 10^5 $ ). The second line of input contains two integers $ x $ and $ y $ ( $ 1\le x,y\le 10^6 $ ). The third line of input contains $ n $ integers $ b_1,b_2,\ldots,b_n $ ( $ 1\le b_i\le 10^6 $ ). This is followed by $ q $ lines. Each of these $ q $ lines contains three integers. The first integer $ op $ is either $ 1 $ or $ 2 $ . - If it is $ 1 $ , it is followed by two integers $ k $ , $ v $ ( $ 1\le k\le n $ , $ 1\le v\le 10^6 $ ). It means that you should change $ b_k $ to $ v $ . - If it is $ 2 $ , it is followed by two integers $ l $ , $ r $ ( $ 1\le l

For each query of type $ 2 $ , print one real number — the answer to the query. Your answer is considered correct if its absolute error or relative error does not exceed $ 10^{-9} $ .

Let's analyse the sample. In the first query, we are asked to compute $ f([3,1,1,4]) $ . The answer is $ 3.5 $ . One optimal sequence of operations is: - In the first $ 1.5 $ seconds do the second operation with $ i=1 $ . - In the next $ 2 $ seconds do the first operation with $ i=3 $ . In the third query, we are asked to compute $ f([1,1,1]) $ . The answer is $ 1 $ . One optimal sequence of operations is: - In the first $ 0.5 $ seconds do the second operation with $ i=1 $ . - In the next $ 0.5 $ seconds do the first operation with $ i=2 $ .