评级估计器

题目描述

你参加 $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$ 个查询,请按输入顺序处理所有查询。

每个查询给出两个整数 $c,x$。首先,将第 $c$ 场比赛的表现值预测修改为 $x$。(该修改是持久的。)然后,假设你在全部 $N$ 场比赛中都获得了当前预测值所对应的表现值,输出所有比赛结束后的最终评级。

输入格式

输入按以下格式从标准输入给出,其中 $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}$ 时,该输出被视为正确。

样例

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

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)$。

第一个查询将 $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$,第一行应输出 $6$。

数据范围

• $1 \le N \le 5 \times 10^5$
• $1 \le B \le 10^9$
• $1 \le Q \le 10^5$
• $0 \le a_i \le 10^9$
• $1 \le c \le N$
• $0 \le x \le 10^9$
• 输入中的所有值均为整数