CF1461D Divide and Summarize

Mike 收到一个长度为 $n$ 的数组 $a$ 作为生日礼物，他决定测试这个数组有多“漂亮”。 如果存在一种方式，经过若干次（可以为零次）切分操作后，能够得到一个元素和为 $s_i$ 的数组，则该数组通过第 $i$ 次漂亮性测试。 数组切分操作的定义如下： - 设 $mid = \left\lfloor\frac{\max(array) + \min(array)}{2}\right\rfloor$，其中 $\max$ 和 $\min$ 分别表示数组中的最大值和最小值。也就是说，$mid$ 是最大值与最小值之和除以 $2$ 并向下取整。 - 然后将数组分为两部分 $\mathit{left}$ 和 $\mathit{right}$。$\mathit{left}$ 包含所有小于等于 $mid$ 的元素，$\mathit{right}$ 包含所有大于 $mid$ 的元素。$\mathit{left}$ 和 $\mathit{right}$ 中的元素顺序与原数组保持一致。 - 第三步，选择保留 $\mathit{left}$ 或 $\mathit{right}$ 中的一个数组，丢弃另一个。被选中的数组替换当前数组，未被选中的数组永久丢弃。 你需要帮助 Mike 判断 $q$ 次漂亮性测试的结果。 注意，每次漂亮性测试都是针对原始数组 $a$ 进行的，因此每次测试都从初始数组 $a$ 开始。也就是说，第一次切分（如果需要）总是在数组 $a$ 上进行。

每个测试包含一个或多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 100$）。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$），分别表示数组 $a$ 的长度和漂亮性测试的次数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \le a_i \le 10^6$），表示数组 $a$ 的内容。 接下来的 $q$ 行，每行包含一个整数 $s_i$（$1 \le s_i \le 10^9$），表示 Mike 希望在第 $i$ 次测试中得到的元素和。 保证所有测试用例中 $n$ 的总和与 $q$ 的总和不超过 $10^5$（$\sum n, \sum q \le 10^5$）。

输出 $q$ 行，每行输出一次漂亮性测试的结果。如果通过测试，输出 "Yes"；否则输出 "No"。

第一个测试用例的解释： 1. 可以通过如下方式得到元素和为 $s_1 = 1$ 的数组： 1.1 $a = [1, 2, 3, 4, 5]$，$mid = \frac{1+5}{2} = 3$，$\mathit{left} = [1, 2, 3]$，$\mathit{right} = [4, 5]$。选择保留 $\mathit{left}$。 1.2 $a = [1, 2, 3]$，$mid = \frac{1+3}{2} = 2$，$\mathit{left} = [1, 2]$，$\mathit{right} = [3]$。选择保留 $\mathit{left}$。 1.3 $a = [1, 2]$，$mid = \frac{1+2}{2} = 1$，$\mathit{left} = [1]$，$\mathit{right} = [2]$。选择保留 $\mathit{left}$，此时和为 $1$。 2. 可以证明无法得到元素和为 $s_2 = 8$ 的数组。 3. 可以通过如下方式得到元素和为 $s_3 = 9$ 的数组： 3.1 $a = [1, 2, 3, 4, 5]$，$mid = \frac{1+5}{2} = 3$，$\mathit{left} = [1, 2, 3]$，$\mathit{right} = [4, 5]$。选择保留 $\mathit{right}$，此时和为 $9$。 4. 可以证明无法得到元素和为 $s_4 = 12$ 的数组。 5. 可以通过如下方式得到元素和为 $s_5 = 6$ 的数组： 5.1 $a = [1, 2, 3, 4, 5]$，$mid = \frac{1+5}{2} = 3$，$\mathit{left} = [1, 2, 3]$，$\mathit{right} = [4, 5]$。选择保留 $\mathit{left}$，此时和为 $6$。 第二个测试用例的解释： 1. 可以证明无法得到元素和为 $s_1 = 1$ 的数组。 2. 可以通过如下方式得到元素和为 $s_2 = 2$ 的数组： 2.1 $a = [3, 1, 3, 1, 3]$，$mid = \frac{1+3}{2} = 2$，$\mathit{left} = [1, 1]$，$\mathit{right} = [3, 3, 3]$。选择保留 $\mathit{left}$，此时和为 $2$。 3. 可以证明无法得到元素和为 $s_3 = 3$ 的数组。 4. 可以通过如下方式得到元素和为 $s_4 = 9$ 的数组： 4.1 $a = [3, 1, 3, 1, 3]$，$mid = \frac{1+3}{2} = 2$，$\mathit{left} = [1, 1]$，$\mathit{right} = [3, 3, 3]$。选择保留 $\mathit{right}$，此时和为 $9$。 5. 元素和为 $s_5 = 11$ 可以不经过任何切分操作直接得到，因为数组的总和就是 $11$。 由 ChatGPT 4.1 翻译