C - 最小值之和查询（Sum of Min Query）

• ​时间限制​：2 sec
• ​内存限制​：1024 MiB
• ​分值​：300 points

题目描述

给定两个长度为 NN 的整数序列

$A=(A_1,A_2,\dots,A_N),\quad B=(B_1,B_2,\dots,B_N)$ .接下来有 Q 次操作，按顺序处理。第 ii 次操作给出一个字符 $c\_i 与整数 X_i, V_i$。

• 若 $c_i = \texttt{'A'}，则将 A_{X_i}$ 改为 $V_i$；
• 若 $c_i = \texttt{'B'}，则将 B_{X_i}$改为 $V_i$。

完成该次修改后，输出

$\sum_{k=1}^{N} \min(A_k,B_k)$的值。

输入格式

N Q
A1 A2 … AN
B1 B2 … BN
c1 X1 V1
c2 X2 V2
…
cQ XQ VQ

输出格式

输出共 Q 行。第 i 行输出第 i 次操作后的 $\sum_{k=1}^{N} \min(A_k, B_k)$。

约束

• $1 \le N,Q \le 2\times10^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$
• 所有输入均为整数

注：输入中的下标 $X_i$ 为 ​1-based​。

样例 1

输入

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

输出

7
9
9

说明

• 操作 1 后：$A=(3,3,4,1), B=(2,7,1,8)$ $\min 逐项为 (2,3,1,1)，和为 7$。
• 操作 2 后：$A=(3,3,4,1)\, B=(2,7,3,8)$ $\min 逐项为 (2,3,3,1)，和为 9。$
• 操作 3 后：$A=(7,3,4,1)\, B=(2,7,3,8)$ $\min 逐项为 (2,3,3,1)，和为 9。$

样例 2

输入

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

输出

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

输出

421
420
420