Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 475 点
問題文
長さ 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 に変更する。
制約
- 入力は全て整数
- 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 です。
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.