統計において、データの散らばり度合いを表す数である分散について説明しよう。

数列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) が呼び出される前に1度だけ呼び出される。このプロシージャは戻り値を持たない。

• 次のパラメータを持つプロシージャ update(i, x):

  • i -- 値が変化する数列の項の番号。0 ≦ i ＜ N を仮定してよい。
  • x -- 値が変化した後の i 番目の項の値。0 ≦ x ≦ 10 000 を仮定してよい。このプロシージャは複数回呼び出される。1回の呼び出しは1回の数列の値の変化に対応する。このプロシージャは戻り値を持たない。

• 次のパラメータを持つプロシージャ variance(i, j):

  • i -- 分散を計算したい区間のはじめの項の番号。 0 ≦ i ＜ N を仮定してよい。
  • j -- 分散を計算したい区間の最後の項の番号。 i ≦ j ＜ N を仮定してよい。

  このプロシージャは複数回呼び出される。それぞれの呼び出しに大して i 番目の項から j 番目の項(両端も含む)までの**(j - i + 1)個の値を母集団としたときの分散**を戻り値として返す必要がある。小数点以下の値は切り捨てて整数値にして返すこと。

例

N = 3, A[i] の初期値が

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

小課題

以下、1回の実行において 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, ...
  **注意:**採点プログラムのサンプルは次の書式の入力を読み込む。
  • 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 行目には3つの整数 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, ...
  **注意:**採点プログラムのサンプルは次の書式の出力を書き出す。
  • 1 行目から Q 行目: 0 ≦ i ＜ Q に対し、i+1 行目には i 回目の variance 呼び出しの際に返されるべき戻り値が書かれている。

---

• Problem Proposal: qnighy
• Problem Statement: qnighy

---

Source Name

IJPC 2012 Practice

---