AT_abc292_h [ABC292Ex] Rating Estimator

题目描述

你将参加 $N$ 场比赛。比赛按照举办顺序分别称为第 $1$ 场、第 $2$ 场，……，第 $N$ 场比赛。

每参加一场比赛，你会获得一个称为“表现值”的分数。第 $i$ 场比赛获得的表现值记为 $P_i$。

此外，你有一个称为“Rating”的数值。Rating 会根据比赛中的表现值发生变化。参加比赛前，Rating 的初始值为 $0$，在参加完第 $n$ 场比赛后，Rating 会变为 $\frac{1}{n}\left(\sum_{i=1}^n P_i\right)$。

但是，如果你的 Rating 一旦达到 $B$ 及以上，那么之后即使继续参加比赛，Rating 也不会再发生变化。

你决定在比赛前预测每场比赛的表现值。初始时，第 $i$ 场比赛的表现值预测为 $a_i$。现在有 $Q$ 个查询，请按输入顺序依次处理。

每个查询给出两个整数 $c,x$。你需要先将第 $c$ 场比赛的表现值预测改为 $x$（这个更改是永久的）。然后，假设你在 $N$ 场比赛中都获得了当前预测的表现值，输出参加完所有比赛后的 Rating 值。

输入格式

输入按以下格式从标准输入读入。$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$
$\dots$
$c_Q$ $x_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

只要你的输出与真值的绝对误差或相对误差不超过 $10^{-9}$，就会被判定为正确。

输入输出样例 #1

输入 #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

说明/提示

数据范围

• $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$
• 输入的所有数均为整数

样例解释 1

初始时，$(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)$。
此时，如果每场比赛的表现值都为 $a_i$，你的 Rating 变化如下：

• 初始时，Rating 为 $0$。
• 第 1 场比赛结束后，Rating 变为 $5 / 1 = 5$。
• 第 2 场比赛结束后，Rating 变为 $(5 + 1) / 2 = 3$。
• 第 3 场比赛结束后，Rating 变为 $(5 + 1 + 9) / 3 = 5$。
• 第 4 场比赛结束后，Rating 变为 $(5 + 1 + 9 + 9) / 4 = 6$。
• 之后，Rating 不再变化，因为第 4 场比赛结束后 Rating 已经达到 $B$ 及以上。 因此，全部比赛结束后的 Rating 为 $6$，所以第 1 行输出 $6$。

由 ChatGPT 4.1 翻译