/ 
Time Limit: 3 sec / Memory Limit: 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.