C - Sum of Min Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N) が与えられます。

Q 個のクエリが与えられるので順に処理してください。 i 番目 (1\le i\le Q) のクエリは以下で説明されます。

文字 c_i と整数 X_i,V_i が与えられる。 c_i= A ならば A_{X_i} を、 c_i= B ならば B_{X_i} を V_i に変更する。その後、 \displaystyle \sum_{k=1}^N \min(A_k,B_k) を出力する。

制約

  • 1\le N,Q \le 2 \times 10^5
  • 1\le A_i,B_i \le 10^9
  • c_i は A か B のいずれか
  • 1\le X_i \le N
  • 1\le V_i \le 10^9
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
c_1 X_1 V_1
c_2 X_2 V_2
\vdots
c_Q X_Q V_Q

出力

Q 行出力せよ。 i 行目 (1\le i\le Q) には i 番目のクエリに対する答えを出力せよ。

入力例 1

4 3
3 1 4 1
2 7 1 8
A 2 3
B 3 3
A 1 7

出力例 1

7
9
9

1 番目のクエリでは A=(3,3,4,1),B=(2,7,1,8) となります。したがって、1 行目には \displaystyle \min(3,2)+\min(3,7) + \min(4 , 1)+\min(1,8) = 7 を出力してください。

2 番目のクエリでは A=(3,3,4,1),B=(2,7,3,8) となります。したがって、 2 行目には \displaystyle \min(3,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 を出力してください。

3 番目のクエリでは A=(7,3,4,1),B=(2,7,3,8) となります。したがって、 3 行目には \displaystyle \min(7,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 を出力してください。

入力例 2

1 3
1
1000000000
A 1 1
A 1 1
A 1 1

出力例 2

1
1
1

入力例 3

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

出力例 3

421
420
420

Score : 300 points

Problem Statement

You are given length-N integer sequences: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You are given Q queries to process in order. The i-th query (1\le i\le Q) is described as follows:

You are given a character c_i and integers X_i,V_i. If c_i= A, change A_{X_i} to V_i; if c_i= B, change B_{X_i} to V_i. Then, output \displaystyle \sum_{k=1}^N \min(A_k,B_k).

Constraints

  • 1\le N,Q \le 2 \times 10^5
  • 1\le A_i,B_i \le 10^9
  • c_i is either A or B.
  • 1\le X_i \le N
  • 1\le V_i \le 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
c_1 X_1 V_1
c_2 X_2 V_2
\vdots
c_Q X_Q V_Q

Output

Output Q lines. The i-th line (1\le i\le Q) should contain the answer to the i-th query.

Sample Input 1

4 3
3 1 4 1
2 7 1 8
A 2 3
B 3 3
A 1 7

Sample Output 1

7
9
9

After the 1st query, A=(3,3,4,1),B=(2,7,1,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 1)+\min(1,8) = 7 on the 1st line.

After the 2nd query, A=(3,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 2nd line.

After the 3rd query, A=(7,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(7,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 3rd line.

Sample Input 2

1 3
1
1000000000
A 1 1
A 1 1
A 1 1

Sample Output 2

1
1
1

Sample Input 3

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

Sample Output 3

421
420
420