CF1895E Infinite Card Game

Monocarp 和 Bicarp 正在玩一款卡牌游戏。每张卡牌有两个参数：攻击值和防御值。如果卡牌 $s$ 的攻击值严格大于卡牌 $t$ 的防御值，则称 $s$ 能击败 $t$。 Monocarp 有 $n$ 张卡牌，第 $i$ 张卡牌的攻击值为 $ax_i$，防御值为 $ay_i$。Bicarp 有 $m$ 张卡牌，第 $j$ 张卡牌的攻击值为 $bx_j$，防御值为 $by_j$。 游戏开始时，Monocarp 先手选择一张自己的卡牌并打出。Bicarp 必须用自己的一张能击败该卡牌的卡牌应对。之后，Monocarp 必须用一张能击败 Bicarp 卡牌的卡牌应对。接下来轮到 Bicarp，如此往复。 每当一张卡牌被击败后，它会返回到出牌者手中。这意味着每位玩家始终拥有与游戏开始时相同的卡牌集合。若当前玩家无法用自己的任何卡牌击败对方刚刚打出的卡牌，则游戏结束，该玩家输掉比赛。 如果游戏持续 $100^{500}$ 步，则判为平局。 Monocarp 和 Bicarp 都会采取最优策略。如果某位玩家无论对方如何应对都能获胜，则他会争取胜利。否则，如果他有平局策略，则会争取平局。 你需要计算以下三个值： - Monocarp 的起手选择中，有多少种会导致 Monocarp 获胜； - 有多少种会导致平局； - 有多少种会导致 Bicarp 获胜。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$），表示 Monocarp 的卡牌数量。 第二行包含 $n$ 个整数 $ax_1, ax_2, \dots, ax_n$（$1 \le ax_i \le 10^6$），表示 Monocarp 卡牌的攻击值。 第三行包含 $n$ 个整数 $ay_1, ay_2, \dots, ay_n$（$1 \le ay_i \le 10^6$），表示 Monocarp 卡牌的防御值。 第四行包含一个整数 $m$（$1 \le m \le 3 \cdot 10^5$），表示 Bicarp 的卡牌数量。 第五行包含 $m$ 个整数 $bx_1, bx_2, \dots, bx_m$（$1 \le bx_j \le 10^6$），表示 Bicarp 卡牌的攻击值。 第六行包含 $m$ 个整数 $by_1, by_2, \dots, by_m$（$1 \le by_j \le 10^6$），表示 Bicarp 卡牌的防御值。 输入的额外约束：所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$，$m$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出三个整数： - Monocarp 的起手选择中，会导致 Monocarp 获胜的数量； - 会导致平局的数量； - 会导致 Bicarp 获胜的数量。

由 ChatGPT 4.1 翻译