103064: [Atcoder]ABC306 E - Best Performances
Description
Score : $475$ points
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$.
Input
题意翻译
### 题目描述： 给定长度为 $N$ 的数列 $A=(A_1,A_2,\dots,A_N)$，最开始所有项均为 $0$。 定义函数 $f(A)$ 如下： 将 $A$ 按照降序（即使得 $A$ 为广义单调递减序列）排序得到 $B$。 则 $f(A)=B_1+B_2+\dots+B_K$，其中 $B$ 为排序后的数列，$K$ 为 $A$ 中不为 $0$ 的元素个数。 现在对该数列进行 $Q$ 次更新。对于每次更新，按顺序执行以下操作，并输出此时的 $f(A)$ 值： 将 $A_{X_i}$ 更改为 $Y_i$。Output
问题描述
我们有一个长度为$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$。