← 返回题目列表

Codeforces · 2148/B

B. 激光器

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

有一个 2D 坐标平面,范围从 $$$(0,0)$$$ 到 $$$(x, y)$$$。您位于 $$$(0,0)$$$,并且想要前往 $$$(x, y)$$$。

然而,有$$$n$$$个水平激光,第$$$i$$$个激光连续跨越$$$(0, a_i)$$$到$$$(x, a_i)$$$。此外,还有$$$m$$$垂直激光器,第$$$i$$$个激光器连续跨越$$$(b_i, 0)$$$到$$$(b_i,y)$$$。

您可以向任意方向移动以到达 $$$(x, y)$$$,但您的移动必须是位于平面内的连续曲线。每次穿过垂直或水平激光时,都算作一次穿过。特别是,如果您经过两个激光之间的交点,则算作 两个路口.

例如,如果 $$$x = y = 2$$$、$$$n = m = 1$$$、$$$a = [1]$$$、$$$b = [1]$$$,则移动可以如下:

到达 $$$(x, y)$$$ 所需的最少交叉次数是多少?

输入

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

每个测试用例的第一行包含四个整数 $$$n$$$、$$$m$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5, 2 \leq x ,y \leq 10^9$$$)。

以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \lt a_i \lt y$$$) — 水平激光的 y 坐标。对于所有$$$i \gt 1$$$,保证$$$a_i \gt a_{i-1}$$$。

以下行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \lt b_i \lt x$$$) — 垂直激光的 x 坐标。对于所有$$$i \gt 1$$$,保证$$$b_i \gt b_{i-1}$$$。

保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出达到 $$$(x, y)$$$ 所需的最小交叉数。

示例

输入
复制

2
1 1 2 2
1
1
2 1 100000 100000
42 58
32

输出
复制

2
3