当前没有测试数据。

Ex - Rating Estimator

得分 : $600$ 分

问题描述

你将参加 $N$ 场比赛，编号为 $1$ 到 $N$，按时间顺序。
参赛者在每场比赛中都会得到一个称为性能</strong>的数值。令 $P_i$ 表示第 $i$ 场比赛的性能。
此外，你还有一个称为评分</strong>的数值，根据比赛的性能变化而变化。初始评分为 $0$，第 $n$ 场比赛后的评分是 $\frac{1}{n} \left(\sum_{i=1}^n P_i \right)$。
然而，一旦你的评分达到 $B$ 或更高，后续比赛将不会影响你的评分。

在比赛之前，你已经决定估计每场比赛中的表现。令 $a_i$ 是第 $i$ 场比赛的初始估计表现。按给定的顺序处理 $Q$ 个查询。

在每个查询中，给你两个整数 $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}$，则输出被视为正确。

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$。
• 在第一场比赛后，你的评分将为 $5 / 1 = 5$。
• 在第二场比赛后，你的评分将为 $(5 + 1) / 2 = 3$。
• 在第三场比赛后，你的评分将为 $(5 + 1 + 9) / 3 = 5$。
• 在第四场比赛后，你的评分将为 $(5 + 1 + 9 + 9) / 4 = 6$。
• 由于你在第四场比赛后的评分不低于 $B$，你的评分将不再变化。

因此，比赛后你的最终评分为 $6$，应该在第一行打印出来。