2023 蓝桥杯热身赛

Problem P13. 异世界的稳定测试(20分)

果冻凭借着自己曾经所学的计算机组成原理,先是成功用魔法创造出了逻辑门,继而又创造出了魔法运作的计算机。为了机器稳定运转,魔法师需要为其施加尽可能稳定的魔法流。贤者禾枫认为,魔法流的标准差可以判定稳定与否。

n 个魔法师,编号从 1n 递增,第 i 个魔法师能提供大小为 x_i 的魔法流。一开始他们按从 1n 的顺序从左到右排成一队。左边是队首,右边是队尾。

有两种操作:

  1. 移动:将队首前 k 个魔法师从左到右依次取出,按取出顺序逐个放到队尾。
  2. 测试:让当前队伍从左往右第 l 到第 r 个(含第 l,r 个)魔法师输出魔法流,统计输出的标准差 s

贤者会进行多次上述操作,每次操作基于前一次的操作。

设平均数为 \overline{x} ,标准差 s 计算公式为: \overline{x}=\dfrac{\sum_{i=l}^rx_i}{r-l+1},\quad s=\sqrt{\frac{\sum_{i=l}^r(x_i-\overline{x})^2}{r-l+1}}

输入

首先输入一行两个整数 n,m

接下来输入一行 n 个整数,第 i 个整数代表 x_i

接下来输入 m 行,对于第 i 行,若输入两个整数 1\ \ k ,代表进行移动操作;若输入三个整数 2\ \ l\ \ r ,代表进行测试操作。

对于 20\% 分数的数据, 1\le n\le10^3,1\le m\le10^4

对于 100\% 分数的数据,1\le n,m\le10^5,0\le x_i\le10^6,1\le k\le n,1\le l \le r\le n

输出

对于每个测试操作,输出一行一个小数s,代表这次测试的能力值标准差。你的答案被认为是正确的当且仅当你的答案与标准答案的相对误差不超过 10^{-6}

样例

标准输入 复制文本
5 6
1 2 3 4 5
2 2 4
2 2 5
1 2
2 3 4
1 4
2 2 5
标准输出 复制文本
0.816497
1.118034
2.000000
1.479020

提示

对第一个测试, \overline x=\dfrac{2+3+4}3=3,\ s=\sqrt{\dfrac{(2-3)^2+(3-3)^2+(4-3)^2}3}\approx0.816497 对第二个测试, \overline x=\dfrac{2+3+4+5}4=3.5,

s=\sqrt{\dfrac{(2-3.5)^2+(3-3.5)^2+(4-3.5)^2+(5-3.5)^2}4}\approx1.118034

对第一次移动,移动后从左到右魔法师能力值为3,4,5,1,2

对第三个测试, \overline x=\dfrac{5+1}2=3,\ s=\sqrt{\dfrac{(5-3)^2+(1-3)^2}2}=2 对第二次移动,移动后从左到右魔法师能力值为2,3,4,5,1

对第四个测试, \overline x=\dfrac{3+4+5+1}4=3.25,

s=\sqrt{\dfrac{(3-3.25)^2+(4-3.25)^2+(5-3.25)^2+(1-3.25)^2}4}\approx1.479020

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 15
通过 5