← 返回题目列表

AtCoder · abc420_c

E. 最小总和查询

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

分数: 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} to V_i;如果 c_i= B,更改 B_{X_i} to 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 or 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

第一次查询后, A=(3,3,4,1),B=(2,7,1,8)。因此,输出 \displaystyle \min(3,2)+\min(3,7) + \min(4 , 1)+\min(1,8) = 7 第一行。

第二次查询后, A=(3,3,4,1),B=(2,7,3,8)。因此,输出 \displaystyle \min(3,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 在第二行。

第三次查询后, A=(7,3,4,1),B=(2,7,3,8)。因此,输出 \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