Score : $600$ points

问题描述

你将参加从 $1$ 到 $N$ 按时间顺序编号的共 $N$ 场比赛。
在每场比赛中，参与者都会得到一个称为表现值的成绩。设第 $i$ 场比赛的表现值为 $P_i$。
此外，你还有一个名为评分的数值，它会根据你在各场比赛中的表现而变化。初始评分为 $0$，而在完成第 $n$ 场比赛后的评分为 $\frac{1}{n} \left(\sum_{i=1}^n P_i \right)$。
然而，一旦你的评分达到 或超过 $B$，后续的比赛将不会影响你的评分。

在比赛开始前，你决定预估自己在每场比赛中的表现。设 $a_i$ 为你对第 $i$ 场比赛表现的初始预估值。按顺序处理 $Q$ 个查询请求。

对于每个查询，你会得到两个整数 $c$ 和 $x$。首先，将你对第 $c$ 场比赛表现的预估值改为 $x$。（此更改是持久的。）然后，假设你在所有 $N$ 场比赛中均达到了预估的表现，请输出比赛结束后你的最终评分。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You will participate in $N$ contests, numbered $1$ to $N$ in chronological order.
A participant in each contest will be given a value called performance for that contest. Let $P_i$ be the performance for contest $i$.
Additionally, you have a value called rating, which changes according to the performances in contests. The initial rating is $0$, and the rating after contest $n$ is $\frac{1}{n} \left(\sum_{i=1}^n P_i \right)$.
However, once your rating is $B$ or higher, later contests will not affect your rating.

Before the contests, you have decided to estimate your performance in each contest. Let $a_i$ be the initial estimate of your performance in contest $i$. Process $Q$ queries in the order they are given.

In each query, you are given two integers $c$ and $x$. First, change the estimate of your performance in contest $c$ to $x$. (This change is persistent.) Then, assuming that you get the estimated performances in all $N$ contests, print your final rating after the contests.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format, where $c_i$ and $x_i$ are the $c$ and $x$ for the $i$-th query:

$N$ $B$ $Q$

$a_1$ $a_2$ $\dots$ $a_N$

$c_1$ $x_1$

$c_2$ $x_2$

$\vdots$

$c_Q$ $x_Q$

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.
Your output is considered correct if the absolute or relative error from the true answer is at most $10^{-9}$.

Sample Input 1

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

Sample Output 1

6.000000000000000
7.500000000000000
6.333333333333333
5.400000000000000
13.333333333333334
13.333333333333334
100.000000000000000

Initially, $(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 3, 8)$.
The first query changes $a_4$ to $9$, making $(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 9, 8)$.
Here, assuming that your performance in contest $i$ is $a_i$, your rating will change as follows.

• Initially, your rating is $0$.
• After contest $1$, your rating will be $5 / 1 = 5$.
• After contest $2$, your rating will be $(5 + 1) / 2 = 3$.
• After contest $3$, your rating will be $(5 + 1 + 9) / 3 = 5$.
• After contest $4$, your rating will be $(5 + 1 + 9 + 9) / 4 = 6$.
• Your rating will no longer change, because your rating after contest $4$ is not less than $B$.

Thus, your final rating after the contests is $6$, which should be printed in the first line.

update @ 2024/3/10 12:11:47