Ex - Rating Estimator 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

あなたは N 個のコンテストに参加します。コンテストが開催される順にコンテスト 1, コンテスト 2, \dots コンテスト N と呼びます。
各コンテストに参加すると、コンテストごとに パフォーマンス という値が与えられます。コンテスト i で与えられるパフォーマンスを P_i とします。
また、あなたは レーティング という値を持っています。レーティングはコンテストでのパフォーマンスによって変化する値です。コンテストに参加する前のレーティングの値は 0 で、コンテスト n に出た後のレーティングの値は \frac{1}{n} \left(\sum_{i=1}^n P_i \right) に変化します。
ただし、あなたのレーティングが一度 B 以上 になると、それ以降はコンテストに参加してもレーティングは変動しなくなります。

あなたはコンテストに出る前に、それぞれのコンテストで得られるパフォーマンスを予測することにしました。はじめ、コンテスト i のパフォーマンスの予測値を a_i とします。クエリが Q 個与えられるので入力される順にすべて処理してください。

各クエリでは 2 個の整数 c, x が与えられます。あなたは、まずコンテスト c のパフォーマンスの予測値を x に変更します。(この変更は永続的です。) そして、あなたが N 個のコンテスト全てで現在の予測値通りのパフォーマンスを得られた場合の、全てのコンテストに参加した後のレーティングの値を答えてください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq B \leq 10^9
  • 1 \leq Q \leq 10^5
  • 0 \leq a_i \leq 10^9
  • 1 \leq c \leq N
  • 0 \leq x \leq 10^9
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ただし、c_i, x_i は i 番目のクエリで与えられる c, x を意味する。

N B Q
a_1 a_2 \dots a_N
c_1 x_1
c_2 x_2
\vdots
c_Q x_Q

出力

Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-9} 以下であれば正解として扱われる。

入力例 1

5 6 7
5 1 9 3 8
4 9
2 10
1 0
3 0
3 30
5 100
1 100

出力例 1

6.000000000000000
7.500000000000000
6.333333333333333
5.400000000000000
13.333333333333334
13.333333333333334
100.000000000000000

はじめ、(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 3, 8) です。
1 番目のクエリによって a_4 が 9 に変更されて (a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 9, 8) となります。
このとき、コンテスト i でパフォーマンス a_i を取った場合のあなたのレーティングの推移は次の通りです。

  • はじめ、レーティングは 0 です。
  • コンテスト 1 が終了した時点でレーティングは 5 / 1 = 5 に変化します。
  • コンテスト 2 が終了した時点でレーティングは (5 + 1) / 2 = 3 に変化します。
  • コンテスト 3 が終了した時点でレーティングは (5 + 1 + 9) / 3 = 5 に変化します。
  • コンテスト 4 が終了した時点でレーティングは (5 + 1 + 9 + 9) / 4 = 6 に変化します。
  • 以降、レーティングの値は変化しません。なぜならば、4 番目のコンテストが終了した時点でレーティングが B 以上の値になっているからです。

よって、全てのコンテストが終了した時点でのレーティングは 6 なので、1 行目にはこれを出力します。

Score : 600 points

Problem Statement

You will participate in N contests, numbered 1 to N in chronological order.
A participant in each contest will be given a value called performance for that contest. Let P_i be the performance for contest i.
Additionally, you have a value called rating, which changes according to the performances in contests. The initial rating is 0, and the rating after contest n is \frac{1}{n} \left(\sum_{i=1}^n P_i \right).
However, once your rating is B or higher, later contests will not affect your rating.

Before the contests, you have decided to estimate your performance in each contest. Let a_i be the initial estimate of your performance in contest i. Process Q queries in the order they are given.

In each query, you are given two integers c and x. First, change the estimate of your performance in contest c to x. (This change is persistent.) Then, assuming that you get the estimated performances in all N contests, print your final rating after the contests.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq B \leq 10^9
  • 1 \leq Q \leq 10^5
  • 0 \leq a_i \leq 10^9
  • 1 \leq c \leq N
  • 0 \leq x \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format, where c_i and x_i are the c and x for the i-th query:

N B Q
a_1 a_2 \dots a_N
c_1 x_1
c_2 x_2
\vdots
c_Q x_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.
Your output is considered correct if the absolute or relative error from the true answer is at most 10^{-9}.

Sample Input 1

5 6 7
5 1 9 3 8
4 9
2 10
1 0
3 0
3 30
5 100
1 100

Sample Output 1

6.000000000000000
7.500000000000000
6.333333333333333
5.400000000000000
13.333333333333334
13.333333333333334
100.000000000000000

Initially, (a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 3, 8).
The first query changes a_4 to 9, making (a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 9, 8).
Here, assuming that your performance in contest i is a_i, your rating will change as follows.

  • Initially, your rating is 0.
  • After contest 1, your rating will be 5 / 1 = 5.
  • After contest 2, your rating will be (5 + 1) / 2 = 3.
  • After contest 3, your rating will be (5 + 1 + 9) / 3 = 5.
  • After contest 4, your rating will be (5 + 1 + 9 + 9) / 4 = 6.
  • Your rating will no longer change, because your rating after contest 4 is not less than B.

Thus, your final rating after the contests is 6, which should be printed in the first line.