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