← 返回题目列表

Codeforces · 1569/D

D. 不方便的配对

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

有一个城市可以表示为一个方形网格,其角点为 $$$(0, 0)$$$ 和 $$$(10^6, 10^6)$$$。

该城市有 $$$n$$$ 垂直街道和 $$$m$$$ 水平街道穿过整个城市,即。 e.第 $$$i$$$ 垂直街道从 $$$(x_i, 0)$$$ 到 $$$(x_i, 10^6)$$$,第 $$$j$$$ 水平街道从 $$$(0, y_j)$$$ 到 $$$(10^6, y_j)$$$。

所有街道都是双向的。城市的边界也是街道。

有 $$$k$$$ 人留在街上:在 $$$(x_p, y_p)$$$ 点的第 $$$p$$$ 人(因此 $$$x_p$$$ 等于某个 $$$x_i$$$ 或 $$$y_p$$$ 等于某个 $$$y_j$$$,或两者兼而有之)。

假设,如果从一个人到另一个人(仅通过街道)的最短路径严格大于他们之间的曼哈顿距离,那么两个人就形成了一对不方便的对。

计算不方便配对的人数($$$(x, y)$$$ 和 $$$(y, x)$$$ 是同一对)。

让我们回想一下点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的曼哈顿距离是 $$$|x_1 - x_2| + |y_1 - y_2|$$$。

输入

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

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$; $$$2 \le k \le 3 \cdot 10^5$$$) — 垂直和水平街道的数量和人数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$0 = x_1 < x_2 < \dots < x_{n - 1} < x_n = 10^6$$$) — 垂直街道的 $$$x$$$ 坐标。

第三行包含 $$$m$$$ 整数 $$$y_1, y_2, \dots, y_m$$$ ($$$0 = y_1 < y_2 < \dots < y_{m - 1} < y_m = 10^6$$$) — 水平街道的 $$$y$$$ 坐标。

接下来的 $$$k$$$ 行包含人员描述。第 $$$p$$$ 行包含两个整数 $$$x_p$$$ 和 $$$y_p$$$ ($$$0 \le x_p, y_p \le 10^6$$$; $$$x_p \in \{x_1, \dots, x_n\}$$$ 或 $$$y_p \in \{y_1, \dots, y_m\}$$$) —第 $$$p$$$ 人的坐标。所有点都是不同的。

它保证$$$n$$$的总和不超过$$$2 \cdot 10^5$$$,$$$m$$$的总和不超过$$$2 \cdot 10^5$$$,$$$k$$$的总和不超过$$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印不方便对的数量。

示例

输入 #1

2
2 2 4
0 1000000
0 1000000
1 0
1000000 1
999999 1000000
0 999999
5 4 9
0 1 2 6 1000000
0 4 8 1000000
4 4
2 5
2 2
6 3
1000000 1
3 8
5 8
8 8
6 8

输出 #1

2
5

注意

第二个测试用例如下图所示:

例如,点 $$$3$$$ 和 $$$4$$$ 形成一个不方便的对,因为它们之间的最短路径(显示为红色且等于 $$$7$$$)大于其曼哈顿距离(等于 $$$5$$$)。

点 $$$3$$$ 和 $$$5$$$ 也形成一对不方便的对:等于 $$$1000001$$$(显示为绿色)的最短路径大于等于 $$$999999$$$ 的曼哈顿距离。

但是点 $$$5$$$ 和 $$$9$$$ 不会形成不方便的对,因为最短路径(显示为紫色)等于其曼哈顿距离。