← 返回题目列表

AtCoder · arc210_b

B. 删除中值运算

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

分数: 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