我们收到报告称此问题评分不正确。
在统计学中,我们来解释一下方差,它是一个表示数据分散程度的数字。
当存在序列 a[1], a[2], …, a[n],
- 平均值 m 是 a[1] 到 a[n] 之和除以 n。
- 对于每个a[k],计算与m之差的平方,并将总和除以n,即方差(σ^2)。
我想计算数列上某个区间的方差。
課題
此处的编号规则 A[0], A[1], ... A[N-1] 有。第一 初始化(N,A) 通过 给出了 A 的初始值。
执行以下程序:
- 具有以下参数的过程 初始化(N,A):
- N -- 序列的长度。序列中的每一项都有 0 它们的编号最大为 N-1 它们用不同的整数编号,最大为 。
- A -- 表示序列中每一项的整数数组。0 ≤ i < N 对于 反对 1 ≤ A[i] ≤ 10 000 可以假设为 。
- 具有以下参数的过程 更新(i,x):
- i -- 序列中值发生变化的项的编号。0 ≤ i < N 对于 。
- x -- 值改变后 第 i 项的值。0 ≤ x ≤ 10 000 。
- 具有以下参数的过程 方差(i,j)
在调用:
- i -- 要计算方差的区间第一项的编号。 0 ≤ i < N 对于 。
- j -- 要计算方差的区间中最后一项的编号。 i ≤ j < N 。
例
N = 3, A[i] 的初始值为
| A = 考虑 | 0 |
| 12 | |
| 6 |
的情况。
一、流程 初始化 。然后多次 更新 或 方差 对 的调用以任意顺序发生。以下是调用和正确返回值的示例:
| 参数 | 返回值 |
|---|---|
| 方差(0, 2) | 24 |
| 方差(1, 2) | 9 |
| 更新(2, 0) | 无 |
| 方差(0, 2) | 32 |
| 方差(1, 2) | 36 |
| 更新(1, 11) | 无 |
| 方差(0, 2) | 26 |
小課題
下面,在一次执行中 每个 更新 和 将其放在 方差 对 被调用的次数 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/(原型: 方差.zip)
- 参赛者实现的文件:variance.cpp
- 提交文件接口:variance.h
- 评分程序示例:grader.cpp
- 评分程序的示例输入:grader.in.1、grader.in.2、...
注意:示例评分程序按以下格式读取输入。- 1 行目: N
- 2 行目: N 整数 A[0], A[1], ..., A[N-1] 有 用空格分隔。A[i] 是一个数字序列。 表示第 i 项的初始值。
- 3 行目: 整数 M。M 是P+Q 等于 。
- 从第 4 行开始 M+3 行目: 0 ≤ i < M ,i+4 行有三个整数 T[i], X[i], Y[i] 用空格分隔。T[i] = 0 当什么时候 i 时间 更新(X[i],Y[i]) 拨打电话 ,T[i] = 1什么时候 i 时间 方差(X[i], Y[i]) 调用 。
- 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
注意:示例评分程序按以下格式写入输出。- 从第 1 行开始 Q 行目: 0 ≤ i < Q ,i+1 在线 i 第 方差 对 写入调用时应返回的返回值。
- 问题建议:qnighy
- 问题陈述:qnighy