G - Dynamic Scheduling Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 675 点

問題文

長さ N の数列 D=(D_1, D_2, \dots, D_N), P=(P_1, P_2, \dots, P_N) が与えられます。

Q 個のクエリを与えられる順に処理してください。クエリは以下の形式で与えられます。

  • c x y : D_c を x に、P_c を y に変更する。そして、次の問題を解いて答えを出力する。

1 から N までの番号がついた N 個の仕事があります。
あなたは今日 (これを 1 日目とする) から 1 日あたり 1 個の仕事を選んで終わらせることを N 日間行います。
仕事 i は D_i 日目までに終わらせると P_i の報酬を貰えます。(D_i 日目までに終わらせなかった場合は何も無い)
仕事をやる順番を上手く選んだ時の報酬の総和の最大値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq D_i \leq N
  • 1 \leq P_i \leq 10^9
  • 1 \leq c \leq N
  • 1 \leq x \leq N
  • 1 \leq y \leq 10^9
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

N Q
D_1 D_2 \dots D_N
P_1 P_2 \dots P_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の形式で与えられる。

c x y

出力

Q 行出力せよ。i 行目には i 番目のクエリの答えを出力せよ。

入力例 1

3 2
1 2 3
3 6 3
3 1 4
2 3 9

出力例 1

10
13

1 番目のクエリは次のようになります。

  • D_3 を 1 に、P_3 を 4 に更新する。D = (1, 2, 1), P = (3, 6, 4) になる。
  • 小問題では、1 日目に仕事 3 を、2 日目に仕事 2 を、3 日目に仕事 1 を行うという手順が最適な手順の 1 つで、この時の報酬の総和は 10 であるから、これを出力する。

2 番目のクエリは次のようになります。

  • D_2 を 3 に、P_2 を 9 に更新する。D = (1, 3, 1), P = (3, 9, 4) になる。
  • 小問題では、1 日目に仕事 3 を、2 日目に仕事 1 を、3 日目に仕事 2 を行うという手順が最適な手順の 1 つで、この時の報酬の総和は 13 であるから、これを出力する。

入力例 2

5 1
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1000000000

出力例 2

5000000000

入力例 3

10 10
6 2 4 1 5 1 6 6 5 3
45 65 71 52 86 52 48 60 40 98
5 6 5
8 4 34
6 7 83
1 3 21
7 5 85
7 4 51
8 2 81
2 7 54
6 1 5
8 6 30

出力例 3

394
379
462
457
459
414
443
479
401
396

Score : 675 points

Problem Statement

You are given two sequences of length N: D=(D_1, D_2, \dots, D_N) and P=(P_1, P_2, \dots, P_N).

Process Q queries in the order they are given. Each query is given in the following format:

  • c x y: Change D_c to x and P_c to y. Then, solve the following problem and print the answer.

There are N jobs numbered 1 to N.
Starting from today (consider this as day 1), you will choose and complete one job per day for N days.
If you complete job i on or before day D_i, you will receive a reward of P_i. (If you do not complete it by day D_i, you get nothing.)
Find the maximum total reward you can achieve by choosing the optimal order of completing the jobs.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq D_i \leq N
  • 1 \leq P_i \leq 10^9
  • 1 \leq c \leq N
  • 1 \leq x \leq N
  • 1 \leq y \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format. Here, \mathrm{query}_i denotes the i-th query.

N Q
D_1 D_2 \dots D_N
P_1 P_2 \dots P_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format.

c x y

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

3 2
1 2 3
3 6 3
3 1 4
2 3 9

Sample Output 1

10
13

The first query is as follows:

  • Update D_3 to 1 and P_3 to 4. Now, D = (1, 2, 1) and P = (3, 6, 4).
  • In the subproblem, one optimal procedure is to complete job 3 on day 1, job 2 on day 2, and job 1 on day 3. The total reward is 10, so print 10.

The second query is as follows:

  • Update D_2 to 3 and P_2 to 9. Now, D = (1, 3, 1) and P = (3, 9, 4).
  • In the subproblem, one optimal procedure is to complete job 3 on day 1, job 1 on day 2, and job 2 on day 3. The total reward is 13, so print 13.

Sample Input 2

5 1
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1000000000

Sample Output 2

5000000000

Sample Input 3

10 10
6 2 4 1 5 1 6 6 5 3
45 65 71 52 86 52 48 60 40 98
5 6 5
8 4 34
6 7 83
1 3 21
7 5 85
7 4 51
8 2 81
2 7 54
6 1 5
8 6 30

Sample Output 3

394
379
462
457
459
414
443
479
401
396