← 返回题目列表

AtCoder · abc292_h

Ex. 评级估算器

中文机器翻译题面 查看原题

分数: 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,应打印在第一行。