分数: 475 点
问题陈述
我们有一个序列 A=(A_1,A_2,\dots,A_N) 长度 N。 最初,所有条款都是 0.
使用整数 K 在输入中给出,我们定义一个函数 f(A) 如下:
- 让 B 为排序得到的序列 A 按降序排列(使其变为单调非递增)。
- 然后,让 f(A)=B_1 + B_2 + \dots + B_K.
我们考虑申请 Q 更新了该序列。
对序列应用以下操作 A 为 i=1,2,\dots,Q 按此顺序,并打印该值
每次更新后的 f(A) 。
- 更改 总共 A_{X_i} to 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- 第行应包含该值 f(A) 作为整数,当 i-第次更新已结束。
示例输入 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-st 更新使 A=(5, 0,0,0)。 现在, f(A)=5.
- 的 2-nd 更新使 A=(5, 1,0,0)。 现在, f(A)=6.
- 的 3-rd 更新使 A=(5, 1,3,0)。 现在, f(A)=8.
- 的 4-th 更新使 A=(5, 1,3,2)。 现在, f(A)=8.
- 的 5-th 更新使 A=(5,10,3,2)。 现在, f(A)=15.
- 的 6-th 更新使 A=(0,10,3,2)。 现在, f(A)=13.
- 的 7-th 更新使 A=(0,10,3,0)。 现在, f(A)=13.
- 的 8-th 更新使 A=(0,10,1,0)。 现在, f(A)=11.
- 的 9-th 更新使 A=(0, 0,1,0)。 现在, f(A)=1.
- 的 10-th 更新使 A=(0, 0,0,0)。 现在, f(A)=0.