#ijpcvariance. [ijpc_variance]分散 (Variance)
[ijpc_variance]分散 (Variance)
分散计算问题
在统计学中，分散是用来表示数据的离散程度的数字。
假设有数列 a[1], a[2], ..., a[n]，
- 从 a[1] 到 a[n] 的总和除以 n 得到的结果是平均值 m。
- 对于每个 a[k]，计算它与 m 的差的平方，并将所有差的平方相加，然后除以 n 得到的结果就是方差 (σ^2)。
现在我们想要计算数列的某个区间的方差。
任务
给定一个数列 A[0], A[1], ... A[N-1]。首先通过调用 init(N, A) 来初始化数列 A 的值。
请实现以下几个函数：
-
函数 init(N, A)，该函数带有以下参数：
- N -- 数列的长度。假设数列中的每一项都被分配了从 0 到 N-1 的不同整数作为编号。
- A -- 由整数构成的数组，表示数列的各个项。可以假设对于每个 0 ≦ i ＜ N，都有 1 ≦ A[i] ≦ 10,000。
该函数在调用一次 update(i, x) 或 variance(i, j) 之前只会被调用一次。该函数没有返回值。
-
函数 update(i, x)，该函数带有以下参数：
- i -- 数列中发生变化的项的编号。可以假设 0 ≦ i ＜ N。
- x -- 第 i 项变化后的值。可以假设 0 ≦ x ≦ 10,000。该函数会被多次调用。每次调用对应数列中某个值的变化。该函数没有返回值。
-
函数 variance(i, j)，该函数带有以下参数：
- i -- 想要计算方差的区间的起始项的编号。可以假设 0 ≦ i ＜ N。
- j -- 想要计算方差的区间的最后一项的编号。可以假设 i ≦ j ＜ N。
该函数会被多次调用。每次调用都需要返回从第 i 项到第 j 项（包括两端）共 (j - i + 1) 个值作为样本时的方差。将小数部分舍去取整数。
示例
考虑一个初始值为
A =
0
12
6
的数列，其中 N = 3。
首先，函数 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
子任务
在一次执行中，update 和 variance 的调用次数分别为 P 和 Q。
子任务 1 (50 分)
- 1 ≦ N ≦ 1,000
- 1 ≦ P+Q ≦ 1,000
子任务 2 (50 分)
- 1 ≦ N ≦ 100,000
- 1 ≦ P+Q ≦ 100,000
实现细节
限制
- CPU 时间限制：5 秒
- 内存限制：64 MB
**注意：**没有规定堆栈大小的限制。堆栈使用的内存将计入总内存使用量。
接口 (API)
- 实现文件夹：variance/ (原型：variance.zip)
- 参赛者实现的文件：variance.cpp
- 提交文件的接口：variance.h
- 评分程序示例：grader.cpp
- 输入示例：grader.in.1, grader.in.2, ...
**注意：**评分程序示例读取的输入具有以下格式：- 第一行：N
- 第二行：用空格分隔的 N 个整数 A[0], A[1], ..., A[N-1]。A[i] 表示数列中第 i 项的初始值。
- 第三行：一个整数 M，表示 P+Q。
- 第四行到第 M+3 行：对于 0 ≦ i ＜ M，第 i+4 行包含三个整数 T[i], X[i], Y[i]，用空格分隔。当 T[i] = 0 时，表示第 i 次调用为 update(X[i], Y[i])；当 T[i] = 1 时，表示第 i 次调用为 variance(X[i], Y[i])。
- 对于给定的输入示例，评分程序示例期望输出：grader.expect.1, grader.expect.2, ...
**注意：**评分程序示例写出了以下格式的输出：- 第一行到第 Q 行：对于 0 ≦ i ＜ Q，第 i+1 行包含第 i 次 variance 调用应返回的结果。
- Problem Proposal: qnighy
- Problem Statement: qnighy