P1471 Variance

While tidying up his old math books, HansBug discovered something curious.

The noob HansBug found a magical sequence in a math book, consisting of $N$ real numbers. He wants to compute the mean and variance of this sequence.

The first line contains two positive integers $N, M$, denoting the number of real numbers in the sequence and the number of operations. The second line contains $N$ real numbers, where the $i$-th real number is the $i$-th term of the sequence. The next $M$ lines each describe an operation, in one of the following three formats: - Operation 1: `1 x y k`, add $k$ (a real number) to every term from the $x$-th to the $y$-th item. - Operation 2: `2 x y`, compute the mean of the subsequence from the $x$-th to the $y$-th item. - Operation 3: `3 x y`, compute the variance of the subsequence from the $x$-th to the $y$-th item.

Output several lines, each containing one real number, which are the results of every Operation 2 or Operation 3 in order. Round all results to $4$ decimal places using standard rounding.

About variance: For a sequence $A$ with $n$ terms, its variance $s^2$ is defined as: $$s^2=\frac{1}{n}\sum\limits_{i=1}^n\left(A_i-\overline A\right)^2$$ where $\overline A$ is the mean of sequence $A$, and $A_i$ is the $i$-th term of sequence $A$. Sample explanation: | Step | Input | Requirement | Sequence | Output | Note | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | - | - | `1 5 4 2 3` | - | - | | $1$ | `2 1 4` | Compute the mean of all numbers in $\left[1,4\right]$ | `1 5 4 2 3` | `3.0000` | Mean $=\left(1+5+4+2\right)\div 4=3.0000$. | | $2$ | `3 1 5` | Compute the variance of all numbers in $\left[1,5\right]$ | `1 5 4 2 3` | `2.0000` | Mean $=\left(1+5+4+2+3\right)\div 5=3$, variance $=\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.0000$. | | $3$ | `1 1 1 1` | Add $1$ to all numbers in $\left[1,1\right]$ | `2 5 4 2 3` | - | - | | $4$ | `1 2 2 -1` | Add $-1$ to all numbers in $\left[2,2\right]$ | `2 4 4 2 3` | - | - | | $5$ | `3 1 5` | Compute the variance of all numbers in $\left[1,5\right]$ | `2 4 4 2 3` | `0.8000` | Mean $=\left(2+4+4+2+3\right)\div 5=3$, variance $=\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.8000$. | Constraints: | Test points | $N$ | $M$ | Note | | :----------: | :----------: | :----------: | :----------: | | $1\sim3$ | $N\le 8$ | $M\le 15$ | - | | $4\sim7$ | $N\le 10^5$ | $M\le 10^5$ | Operation $3$ not included. | | $8\sim10$ | $N\le 10^5$ | $M\le 10^5$ | - | All numbers in the original sequence and all input $k$ are real numbers within the range $[-100, 100]$. Translated by ChatGPT 5