← 返回题目列表

AtCoder · abc306_e

H. 最佳表演

中文机器翻译题面 查看原题

分数: 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.