← 返回题目列表

Codeforces · 2199/D

D. 两个数组

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

序列 $$$[s_1, s_2, \dots, s_k]$$$ 的中位数定义为当序列按非降序排序时出现在位置 $$$\lfloor \frac{k+1}{2} \rfloor$$$ 的元素。例如,序列$$$[4, 5, 6, 1, 2, 2]$$$的中位数是$$$2$$$;序列 $$$[3, 6, 3, 4, 5]$$$ 的中位数是 $$$4$$$。

给定两个数组 $$$[a_1, a_2, \dots, a_n]$$$ 和 $$$[b_1, b_2, \dots, b_m]$$$,按非降序排序。两个数组的长度均为奇数。

在一次操作中,您可以执行以下操作:

  • 选择一个数组并标记一个 奇数 其中元素的数量;
  • 计算 $$$x$$$ — 标记元素的中位数;
  • 删除所有标记的元素;
  • 将 $$$x$$$ 插入到执行操作的数组的任意位置。

你的任务是确定是否可以使数组相等。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由三行组成:

  • 第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$);
  • 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$);
  • 第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_1 \le b_2 \le \dots \le b_m \le 10^9$$$)。

输入的附加限制:

  • 所有测试用例的 $$$(n+m)$$$ 总和不超过 $$$3 \cdot 10^5$$$;
  • 在每个测试用例中,$$$n \bmod 2 = 1$$$ 和 $$$m \bmod 2 = 1$$$。

输出

对于每个测试用例,输出 是 如果可以使数组相等,或者 NO 如果不可能。

示例

输入
复制

3
5 3
1 2 3 4 5
1 3 7
3 5
11 17 19
19 20 26 29 37
1 7
11
1 2 7 9 11 15 17

输出
复制

YES
NO
YES

注意

在第一个示例中,可以通过应用以下操作序列使数组相等:

  1. 对于数组 $$$a = [1, 2, 3, 4, 5]$$$,标记第 $$$2$$$ 个、第 $$$4$$$ 个和第 $$$5$$$ 个元素。他们的中位数是$$$4$$$。我们将它插入到数组的末尾,结果是 $$$a = [1, 3, 4]$$$;
  2. 对于数组 $$$b = [1, 3, 7]$$$,标记所有元素。他们的中位数是$$$3$$$。我们得到数组 $$$b = [3]$$$;
  3. 对于数组 $$$a = [1, 3, 4]$$$,标记所有元素。他们的中位数是$$$3$$$。我们得到数组 $$$a = [3]$$$;
  4. 现在数组 $$$a$$$ 和 $$$b$$$ 相等。