← 返回题目列表

Codeforces · 895/E

E. 闭着眼睛

中文机器翻译题面 查看原题

Vasya 和 Petya 厌倦了学习,所以他们决定玩一个游戏。在游戏开始之前,Vasya 查看由 n 个整数组成的数组 a。一旦他记住了游戏的所有元素,游戏就开始了。 Vasya 闭上眼睛,Petya 执行以下两种动作之一:

1) Petya 表示 4 个整数 l1、r1、l2、r2 — 两个不相交线段的边界。之后,他将 [l1, r1] 段中的一个随机元素与 [l2, r2] 段中的另一个随机元素交换。

2) Petya 向 Vasya 询问 [l, r] 段中 a 的元素之和。

Vasya 是一位数学家,所以他回答 Petya 段中元素之和的数学期望。

你的任务是编写一个程序来回答第二类问题,就像 Vasya 所做的那样。换句话说,您的程序应该为每个第二种类型的查询打印 [l, r] 段中 a 元素总和的数学期望。

输入

第一行包含两个整数 n、q (2 ≤ n ≤ 105, 1 ≤ q ≤ 105) — 数组中的元素数量和需要处理的查询数量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — 数组的元素。

接下来的 q 行包含 Petya 类型 1 或 2 的动作。

如果是类型 1 动作,则该行包含 5 个整数 1、l1、r1、l2、r2 (1 ≤ l1 ≤ r1 ≤ n、1 ≤ l2 ≤ r2 ≤ n)。

如果是类型 2 查询,则该行包含 3 个整数 2、l、r (1 ≤ l ≤ r ≤ n)。

保证至少有一个类型2查询并且段[l1, r1], [l2, r2]没有公共元素。

输出

对于每个类型 2 查询,打印一个实数 - 段中元素总和的数学期望。

如果绝对或相对误差不超过 10 - 4,则您的答案将被视为正确 - 正式而言,如果 $${ \operatorname* { m i n } } ( | x - y |, { \frac { | x - y | } { x } } ) \leq 1 0 ^ { - 4 }$$ 则答案是正确的,其中 x 是陪审团的答案,y 是你的。

示例

输入 #1

4 4
1 1 2 2
1 2 2 3 3
2 1 2
1 1 2 3 4
2 1 2

输出 #1

3.0000000
3.0000000

输入 #2

10 5
1 1 1 1 1 2 2 2 2 2
1 1 5 6 10
2 1 5
1 1 5 6 10
1 1 5 6 10
2 6 10

输出 #2

6.0000000
8.0400000

输入 #3

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

输出 #3

23.0000000
14.0000000
28.0133333
21.5733333
55.0000000