分数: 600 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N 和一个整数序列 B=(B_1,B_2,\ldots,B_M) 长度 M。在这里, N is 甚至.
你被给予 Q 查询。的 q-第一个查询以整数三元组的形式给出 (t_q,i_q,x_q),它执行以下操作。
- If t_q=1:在这种情况下, 1\leq i_q\leq N。此查询发生变化 A_{i_q} to x_q.
- If t_q=2:在这种情况下, 1\leq i_q\leq M。此查询发生变化 B_{i_q} to x_q.
处理每个查询后,找到以下子问题的答案。
初始化多重集 X 与 X=\lbrace A_1,A_2,\ldots,A_N\rbrace。 对于 j=1,2,\ldots,M,执行以下操作:
- 插入 B_j 进入 X。然后,删除其中一个中位数 X 来自 X.
求 中元素的总和 X 当所有操作完成时。
什么是中位数?
当 N 是偶数,多重集的中位数 X 与 N+1 元素是 \left(1+\frac{N}{2}\right)- 元素中按升序排列的第一个值 X.
例如,中位数 X=\lbrace 1, 3, 4, 5, 8\rbrace is 4,以及中位数 X=\lbrace 2,2,2\rbrace is 2.
请注意,在这个问题中,我们考虑中位数的多重集始终具有奇数个元素。
约束
- 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\lbrace 1,2\rbrace
- If t_q=1,那么 1\leq i_q\leq N
- If t_q=2,那么 1\leq i_q\leq M
- 1\leq x_q\leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
4 2 2 5 1 4 3 1 2 1 3 3 2 1 5
示例输出 1
10 13
首先, 1-st 查询使 A=(5,1,3,3) 和 B=(1,2)。在这种情况下,子问题的运算过程如下。
- 初始化 X=\lbrace 5,1,3,3\rbrace=\lbrace 1,3,3,5\rbrace.
- 插入 B_1=1 进入 X, 制作 X=\lbrace 1,1,3,3,5\rbrace。然后,从中删除一个中位数 X, 制作 X=\lbrace 1,1,3,5\rbrace.
- 插入 B_2=2 进入 X, 制作 X=\lbrace 1,1,2,3,5\rbrace。然后,从中删除一个中位数 X, 制作 X=\lbrace 1,1,3,5\rbrace.
中的元素总和 X 当所有操作完成后是 1+1+3+5=10.
接下来, 2-nd 查询使得 A=(5,1,3,3) 和 B=(5,2)。在这种情况下,子问题的运算过程如下。
- 初始化 X=\lbrace 5,1,3,3\rbrace=\lbrace 1,3,3,5\rbrace.
- 插入 B_1=5 进入 X, 制作 X=\lbrace 1,3,3,5,5\rbrace。然后,从中删除一个中位数 X, 制作 X=\lbrace 1,3,5,5\rbrace.
- 插入 B_2=2 进入 X, 制作 X=\lbrace 1,2,3,5,5\rbrace。然后,从中删除一个中位数 X, 制作 X=\lbrace 1,2,5,5\rbrace.
中的元素总和 X 当所有操作完成后是 1+2+5+5=13.
示例输入 2
6 7 5 7 1 2 5 5 3 4 2 5 1 3 3 8 2 1 3 2 7 1 1 3 6 2 4 2 1 5 1
示例输出 2
24 20 21 22 21