103064: [Atcoder]ABC306 E - Best Performances

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$.

问题描述

我们有一个长度为$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$进行以下操作，每次更新后输出该点处的$f(A)$值。

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

约束条件

• 所有输入值都是整数。
• $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$

输入

输入从标准输入以以下格式给出：

$N$ $K$ $Q$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_Q$ $Y_Q$

输出

总共打印$Q$行。第$i$行应该包含当第$i$次更新结束时$f(A)$的整数值。

样例输入1

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

样例输出1

5
6
8
8
15
13
13
11
1
0

在这个输入中，$N=4$，$K=2$。应用了$Q=10$次更新。

• 第1次更新使$A=(5, 0,0,0)$。现在，$f(A)=5$。
• 第2次更新使$A=(5, 1,0,0)$。现在，$f(A)=6$。
• 第3次更新使$A=(5, 1,3,0)$。现在，$f(A)=8$。
• 第4次更新使$A=(5, 1,3,2)$。现在，$f(A)=8$。
• 第5次更新使$A=(5,10,3,2)$。现在，$f(A)=15$。
• 第6次更新使$A=(0,10,3,2)$。现在，$f(A)=13$。
• 第7次更新使$A=(0,10,3,0)$。现在，$f(A)=13$。
• 第8次更新使$A=(0,10,1,0)$。现在，$f(A)=11$。
• 第9次更新使$A=(0, 0,1,0)$。现在，$f(A)=1$。
• 第10次更新使$A=(0, 0,0,0)$。现在，$f(A)=0$。