AT_ijpc_variance.分散 (Variance)

背景

在统计中，方差是表示数据的散乱程度的一个数。

在数列$a_1,a_2,a_3,...,a_n$中：

• 平均数m是指$\frac{a_1+a_2+a_3+...+a_n}n$

• 方差(σ^2)是指$\sum_{k=1}^n|a_k-m|^2$。

我想计算数列上的某个区间的方差。

课题

有个数列$A_0,A_1,A_2,...,A_{n-1}$。首先通过$init(N, A)$给出A的初始值。

请实现以下过程

• 过程$init(N, A)$

  • $N$表示数排的长度。数列的每一项都有不同的整数编号，从$0$到$N-1$。

  • $A$表示数列中各个项的整数排列。假定对于$A$中的任何一个数$A_i$都满足 $1 \leq A_i \leq 10 000$

最初在调用$update(i, x)$或$variance(i, j)$之前只调用该过程一次。这个过程没有返回值。

• 过程$update(i, x)$

  • i表示数组数值变化项。$0 \leq i<N$。

  • x表示变化后的第i项的值。$0 \leq x \leq 10000$

  • 就是将$A_i$的值改成$x$

这个过程被调用多次。一次调用对应于一次数列$A$值的变化。这个过程没有返回值。

• 函数$variance(i, j)$

  • i表示想计算分散的区间开始的一项的下标。$0 \leq i < N$

  • j表示我想计算分散区间的最后一项的下标。$i \leq j < N$

  • 就是计算当前数列中$A_i-A_j$的方差

这个过程被调用多次。当把从第i项到第j项的值(包括端点)。答案记得取整.

例子

$N=3,A=\{0,12,6\}$

首先，过程$init$由上述参数进行调用。然后，以任意顺序执行多个$update$过程或$variance$函数的调用。以下是调用和正确的返回值的示例：

参数	返回值
$variance(0, 2)$	24
$variance(1, 2)$	9
$update(2, 0)$	无
$variance(0, 2)$	32
$variance(1, 2)$	36
$update(1, 11)$	无
$variance(0, 2)$	26

第一行一个整数$N$,表示$A$数组元素个数

第二行接下来$N$个整数$A_0,A_1,A_2,..A_{n-1}$(用空格分隔),$A_i$表示第$i$项的初始值

第三行一个整数$M$,$M$=$P+Q$

第四至第$M+3$行,第$i+4$行输入整数$T_i,X_i,Y_i$(用空格分隔),$T_i=0$表示调用$update(X_i,Y_i)$,$T_i=1$表示调用$variance(X_i,Y_i)$

对于每个$variance$函数的调用，输出结果

数据规模

$50\%$的数据，$1 \leq N \leq 1000,1 \leq P+Q \leq 1000$

另$50\%$的数据,$1 \leq N \leq 100000,1 \leq P+Q \leq 100000$