CF1637E Best Pair

给定一个长度为 $n$ 的数组 $a$。设 $cnt_x$ 表示数组中等于 $x$ 的元素个数。定义 $f(x, y) = (cnt_x + cnt_y) \cdot (x + y)$。 同时给定 $m$ 个坏对 $(x_i, y_i)$。注意，如果 $(x, y)$ 是坏对，则 $(y, x)$ 也是坏对。 你的任务是，在所有满足 $u \neq v$，且该对不是坏对，并且 $u$ 和 $v$ 都在数组 $a$ 中出现过的数对 $(u, v)$ 中，求 $f(u, v)$ 的最大值。保证一定存在这样的数对。

第一行包含一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$，$0 \le m \le 3 \cdot 10^5$），分别表示数组长度和坏对数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组的元素。 接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i < y_i \le 10^9$），表示一个坏对。保证输入中没有重复的坏对。保证 $cnt_{x_i} > 0$ 且 $cnt_{y_i} > 0$。 保证每个测试用例都存在一组 $u \ne v$，且不是坏对，且 $u$ 和 $v$ 都在 $a$ 中出现过。 保证所有测试用例中 $n$ 的总和与 $m$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示该测试用例的答案。

在第一个测试用例中，$3$、$6$、$7$ 在数组中出现。 - $f(3, 6) = (cnt_3 + cnt_6) \cdot (3 + 6) = (3 + 2) \cdot (3 + 6) = 45$。但 $(3, 6)$ 是坏对，所以忽略。 - $f(3, 7) = (cnt_3 + cnt_7) \cdot (3 + 7) = (3 + 1) \cdot (3 + 7) = 40$。 - $f(6, 7) = (cnt_6 + cnt_7) \cdot (6 + 7) = (2 + 1) \cdot (6 + 7) = 39$。 所以答案为 $\max(40, 39) = 40$。 由 ChatGPT 4.1 翻译