Score : $475$ points

问题描述

我们有一个长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$。最初，所有项均为 $0$。

给定一个整数 $K$，我们定义一个函数 $f(A)$ 如下：

• 首先，将序列 $A$ 按降序排序得到序列 $B$（使其单调非增）。
• 然后，令 $f(A)=B_1 + B_2 + \dots + B_K$。

我们考虑对这个序列应用 $Q$ 次更新操作。按照顺序对序列 $A$ 应用以下操作，对于 $i=1,2,\dots,Q$，并在每次更新后输出此时的 $f(A)$ 值。

• 将 $A_{X_i}$ 改为 $Y_i$。

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

Problem Statement

We have a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$. Initially, all the terms are $0$.
Using an integer $K$ given in the input, we define a function $f(A)$ as follows:

• Let $B$ be the sequence obtained by sorting $A$ in descending order (so that it becomes monotonically non-increasing).
• Then, let $f(A)=B_1 + B_2 + \dots + B_K$.

We consider applying $Q$ updates on this sequence.
Apply the following operation on the sequence $A$ for $i=1,2,\dots,Q$ in this order, and print the value $f(A)$ at that point after each update.

• Change $A_{X_i}$ to $Y_i$.

Constraints

• All input values are integers.
• $1 \le K \le N \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• $1 \le X_i \le N$
• $0 \le Y_i \le 10^9$

Input

The input is given from Standard Input in the following format:

$N$ $K$ $Q$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_Q$ $Y_Q$

Output

Print $Q$ lines in total. The $i$-th line should contain the value $f(A)$ as an integer when the $i$-th update has ended.

Sample Input 1

4 2 10
1 5
2 1
3 3
4 2
2 10
1 0
4 0
3 1
2 0
3 0

Sample Output 1

5
6
8
8
15
13
13
11
1
0

In this input, $N=4$ and $K=2$. $Q=10$ updates are applied.

• The $1$-st update makes $A=(5, 0,0,0)$. Now, $f(A)=5$.
• The $2$-nd update makes $A=(5, 1,0,0)$. Now, $f(A)=6$.
• The $3$-rd update makes $A=(5, 1,3,0)$. Now, $f(A)=8$.
• The $4$-th update makes $A=(5, 1,3,2)$. Now, $f(A)=8$.
• The $5$-th update makes $A=(5,10,3,2)$. Now, $f(A)=15$.
• The $6$-th update makes $A=(0,10,3,2)$. Now, $f(A)=13$.
• The $7$-th update makes $A=(0,10,3,0)$. Now, $f(A)=13$.
• The $8$-th update makes $A=(0,10,1,0)$. Now, $f(A)=11$.
• The $9$-th update makes $A=(0, 0,1,0)$. Now, $f(A)=1$.
• The $10$-th update makes $A=(0, 0,0,0)$. Now, $f(A)=0$.

update @ 2024/3/10 08:39:16