Skip to content

1119: 为什么要突发奇想

题目

题目描述

友好的助教在一本数学书里面发现了一个神奇的数列,包含 $N$ 个实数。他突发奇想,就想算算这个数列的平均数方差。可惜这周所有的助教都因为编译器而解体了,没法逐一进行手动计算。但他知道,要是有一棵线段树该有多好,线段树肯定能够帮他高效地完成这一系列的统计问题。

输入格式

第一行包含两个正整数 $N,M$,分别表示数列中实数的个数和操作的个数。

第二行包含 $N$ 个实数,其中第 $i$ 个实数表示数列的第 $i$ 项。

接下来 $M$ 行,每行为一条操作,格式为以下三种之一:

操作 $1$:1 x y k ,表示将第 $x$ 到第 $y$ 项每项加上 $k$,$k$ 为一实数。

操作 $2$:2 x y ,表示求出第 $x$ 到第 $y$ 项这一子数列的平均数。

操作 $3$:3 x y ,表示求出第 $x$ 到第 $y$ 项这一子数列的方差。

输出格式

输出包含若干行,每行为一个实数,即依次为每一次操作 $2$ 或操作 $3$ 所得的结果。

注意:为了避免精度问题,所有的结果都乘以 $100$ 并向零取整之后输出。这将会是一个整数。我们保证这个整数在 int范围内。

样例输入

text 5 5 1.0 5.0 4.0 2.0 3.0 2 1 4 3 1 5 1 1 1 1.0 1 2 2 -1.0 3 1 5

样例输出

text 300 200 80

数据范围

  • 所有输入的实数大小的绝对值都不超过 100。
  • 数据点 $1\sim2$ 满足 $N\le 10^1$ $M\le 10^2$
  • 数据点 $3\sim4$ 满足 $N\le 10^5$ $M\le 10^5$ ,且不包含操作3
  • 数据点 $5\sim7$ 满足 $N\le 10^5$ $M\le 10^5$ ,且不包含操作1
  • 数据点 $8\sim10$ 满足 $N\le 10^5$ $M\le 10^5$

样例说明:

  • 初始数列:1 5 4 2 3
  • 第一次操作:
  • 数列为 1 5 4 2 3
  • 输入 2 1 4, 求 $\left[1,4\right]$ 内所有数字的平均数
  • 平均数 $=\left(1+5+4+2\right)\div 4=3.00$
  • 输出 300
  • 第二次操作:
  • 数列为 1 5 4 2 3
  • 输入 3 1 5,求 $\left[1,5\right]$ 内所有数字的方差
  • 平均数 $=(1 + 5 + 4 + 2 + 3) \div 5 = 3$
  • 方差$=\left(\left(1-3\right)^2+\left(5-3\right)^2+\left(4-3\right)^2+\left(2-3\right)^2+\left(3-3\right)^2\right)\div 5=2.00$
  • 输出 200
  • 第三次操作:
  • 数列为 1 5 4 2 3
  • 输入 1 1 1 1, 将 $\left[1,1\right]$ 内所有数字加 $1$
  • 数列变为 2 5 4 2 3
  • 第四次操作:
  • 数列为 2 5 4 2 3
  • 输入 1 2 2 -1,将 $\left[2,2\right]$ 内所有数字加 $−1$
  • 数列变为 2 4 4 2 3
  • 第五次操作
  • 数列为 2 4 4 2 3
  • 输入 3 1 5,求 $\left[1,5\right]$ 内所有数字的方差
  • 平均数 $= (2 + 4 + 4 + 2 + 3) \div 5 = 3$
  • 方差 $=\left(\left(2-3\right)^2+\left(4-3\right)^2+\left(4-3\right)^2+\left(2-3\right)^2+\left(3-3\right)^2\right)\div 5=0.80$
  • 输出 80

温馨提示:

关于方差:对于一个有 $n$ 项的数列 $A$,其方差 $s^2$ 定义如下: $$ s^2=\frac{1}{n}\sum\limits_{i=1}^n\left(A_i-\overline A\right)^2 $$

其中 $\overline A$ 表示数列 $A$ 的平均数,$A_i$ 表示数列 $A$ 的第 $i$ 项。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!