AT_arc210_b [ARC210B] Remove Median Operations

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$，和一个长度为 $M$ 的整数序列 $B=(B_1,B_2,\ldots,B_M)$。这里，$N$ 是**偶数**。 你会收到 $Q$ 个询问。每个第 $q$ 次询问由三个整数 $(t_q,i_q,x_q)$ 组成，作用如下： - 如果 $t_q=1$：此时 $1\leq i_q\leq N$。这个询问将 $A_{i_q}$ 变为 $x_q$。 - 如果 $t_q=2$：此时 $1\leq i_q\leq M$。这个询问将 $B_{i_q}$ 变为 $x_q$。 每次处理完一个询问后，回答如下子问题： > 初始化多重集 $X$，令 $X=\{A_1,A_2,\ldots,A_N\}$。对于 $j=1,2,\ldots,M$，依次执行如下操作： > > - 将 $B_j$ 插入 $X$，然后从 $X$ 中移除一个中位数。 > > 当所有操作结束后，输出 $X$ 中所有元素的和。 中位数的定义如下：当 $N$ 为偶数时，对于元素个数为 $N+1$ 的多重集 $X$，中位数为按升序排列后第 $\left(1+\frac{N}{2}\right)$ 个值。 例如，$X=\{1,3,4,5,8\}$ 的中位数是 $4$，$X=\{2,2,2\}$ 的中位数是 $2$。 注意本题每次取中位数时多重集 $X$ 的元素总数都是奇数。

输入按如下格式给出： > $N$ $M$ $Q$ > $A_1$ $A_2$ $\cdots$ $A_N$ > $B_1$ $B_2$ $\cdots$ $B_M$ > $t_1$ $i_1$ $x_1$ > $\vdots$ > $t_Q$ $i_Q$ $x_Q$

输出 $Q$ 行。第 $q$ 行应输出处理完第 $q$ 次询问后子问题的答案。

### 样例解释 1 首先，第 $1$ 次询问后 $A=(5,1,3,3)$，$B=(1,2)$。此时按子问题的操作如下： - 初始化 $X=\{5,1,3,3\}=\{1,3,3,5\}$。 - 插入 $B_1=1$，$X$ 变为 $\{1,1,3,3,5\}$。删除中位数 $3$，$X$ 变为 $\{1,1,3,5\}$。 - 插入 $B_2=2$，$X$ 变为 $\{1,1,2,3,5\}$。删除中位数 $2$，$X$ 变为 $\{1,1,3,5\}$。 最终 $X$ 的和为 $1+1+3+5=10$。 接下来，第 $2$ 次询问后 $A=(5,1,3,3)$，$B=(5,2)$。此时操作如下： - 初始化 $X=\{5,1,3,3\}=\{1,3,3,5\}$。 - 插入 $B_1=5$，$X$ 变为 $\{1,3,3,5,5\}$。删除中位数 $3$，$X$ 变为 $\{1,3,5,5\}$。 - 插入 $B_2=2$，$X$ 变为 $\{1,2,3,5,5\}$。删除中位数 $3$，$X$ 变为 $\{1,2,5,5\}$。 最终 $X$ 的和为 $1+2+5+5=13$。 ### 数据范围 - $1\leq N,M,Q\leq 2\times 10^5$ - $N$ 是偶数。 - $1\leq A_i\leq 10^9$ - $1\leq B_i\leq 10^9$ - $t_q\in\{1,2\}$ - 若 $t_q=1$，则 $1\leq i_q\leq N$ - 若 $t_q=2$，则 $1\leq i_q\leq M$ - $1\leq x_q\leq 10^9$ - 所有输入都是整数。 由 ChatGPT 5 翻译