AT_abc306_e [ABC306E] Best Performances

题目描述

有一个长度为 $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$。

输入格式

输入从标准输入按以下格式给出。

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

输出格式

共输出 $Q$ 行。第 $i$ 行输出第 $i$ 次更新结束时的 $f(A)$ 的值。

输入输出样例 #1

输入 #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

说明/提示

数据范围

• 所有输入均为整数。
• $1\leq K\leq N\leq 5\times 10^5$
• $1\leq Q\leq 5\times 10^5$
• $1\leq X_i\leq N$
• $0\leq Y_i\leq 10^9$

样例解释 1

本输入中 $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$。

由 ChatGPT 4.1 翻译