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\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 翻译