分数: 600 点
问题陈述
您将参加 N 竞赛,编号 1 to N 按时间顺序排列。
每次比赛的参与者都会被赋予一个名为 性能
用户的 参加那场比赛。让 P_i 为比赛表演 i.
此外,您还有一个名为 评级
用户的,根据比赛中的表现而变化。初始评级为 0,以及比赛后的评分 n is \frac{1}{n} \left(\sum_{i=1}^n P_i \right).
但是,一旦您的评级 B 或更高,以后的比赛不会影响你的评分。
在比赛之前,您已决定评估您在每场比赛中的表现。让 a_i 是对您在比赛中表现的初步估计 i。工艺流程 Q 按给出的顺序进行查询。
在每个查询中,您都会得到两个整数 c 和 x。首先,改变对你在比赛中表现的估计 c to 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 是 c 和 x 为 i第一个查询:
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).
第一个查询发生变化 a_4 to 9,制作 (a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 9, 8).
在这里,假设您在比赛中的表现 i is 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,应打印在第一行。