思路

• 关键等式：方差可用 $Var = E[X^2] - (E[X])^2$ 计算。只需区间的 $sum$ 与 $sum$ 的平方和 $\sum a_i^2$。

• 数据结构：维护两个树状数组（或线段树）：

  • 一个维护区间和 $S=\sum a_i$。
  • 一个维护平方和 $Q=\sum a_i^2$。

• 操作复杂度：单点修改 $O(log n)$，区间查询 $O(log n)$。

• 计算：查询 $[l,r]$ 时，$m=r-l+1$，$Var = \dfrac{Q}{m} - \left(\dfrac{S}{m}\right)^2$。使用 $64$ 位整型累计，最终用浮点输出。

题目内容

给定 $n$ 名员工的工资序列 $a_1,a_2,...,a_n$ 。

方差 用来度量数据的离散程度，具体见下方名词解释。

现有 $q$ 次操作。每次操作有两种类型：

1.将第 $i$ 名员工的工资修改为 $x$ ;

2.查询区间 $[l,r]$ 内的工资方差。

请处理所有操作，并输出每次查询的结果。

【名词解释】

• 方差：方差 指对于长度为 $m$ 的工资序列 {$b_1,b_2,...,b_m$}，其平均数为

$\bar{b}=\frac{1}{m}\sum^m_{i=1}b_i$

方差定义为 $Var=\frac{1}{m}\sum^m_{i=1}(b_i-\bar{b})^2$

输入描述

第一行输入两个整数 $n$ 和 $q(1≦n,q≦10^5)$ ，分别表示员工数量和操作次数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦10^5)$ ，表示员工的初始工资。

接下来 $q$ 行，每行描述一种操作：

1.当操作类型为 $1$ 时，输入格式为

$1$ $i$ $x(1≦i≦n,1≦x≦10^5)$

表示将第 $i$ 名员工的工资修改 $x$ ；

2.当操作类型为 $2$ 时，输入格式为 $2$ $l$ $r(1≦l≦r≦n)$ 表示查询区间 $[l,r]$ 内的工资方差。

输出描述

对于每次操作类型为 $2$ 的操作，在一行上输出一个实数，表示区间 $[l,r]$ 内的工资方差。

由于实数的计算存在误差，当误差的量级不超过 $10^{-6}$ 时，您的答案都将被接受。具体来说，设您的答案为 $a$ ，标准答案为 $b$ ，当且仅当

$\frac{∣a-b∣}{max(1,∣b∣)}≤10^{-6}$

样例1

输入

5 3
1 2 3 4 5
2 1 5
1 3 10
2 1 5

输出

2.000000
9.840000

说明

在第一个样例中，初始化工资序列为 {$1,2,3,4,5$}。

• 操作 $2$ $1$ $5$ ：区间 $[1,5]$ 的平均数为 $3$ ，方差为 $\frac{(1-3)^2+(2-3)^2+(3-3)^2+(4-3)^2+(5-3)^2}{5}=2$；

• 操作 $1$ $3$ $10$ ：将三名员工工资修改为 $10$ ；

• 操作 $2$ $1$ $5$ ：区间 $[1,5]$ 的平均数为 $4.4$ ，方差为 $\frac{(1-4.4)^2+(2-4.4)^2+(10-4.4)^2+(4-4.4)^2+(5-4.4)^2}{5}=9.84$