CF1196B Odd Sum Segments

给定一个包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ 的数组 $a$。你需要将其划分为恰好 $k$ 个非空且互不相交的子段，使得每个子段的元素和都是奇数（即每个子段内所有元素之和为奇数）。不允许对数组元素进行重排（洗牌）。数组中的每个元素必须且只能属于一个子段。 以下是将长度为 $5$ 的数组划分为 $3$ 个子段（不要求子段和为奇数）的所有可能方式的示例：初始数组为 $[1, 2, 3, 4, 5]$，可以划分为： - $[1], [2], [3, 4, 5]$； - $[1], [2, 3], [4, 5]$； - $[1], [2, 3, 4], [5]$； - $[1, 2], [3], [4, 5]$； - $[1, 2], [3, 4], [5]$； - $[1, 2, 3], [4], [5]$。 当然，可能无法将初始数组划分为恰好 $k$ 个子段，并且每个子段的元素和都是奇数。如果无法做到，请输出 "NO"。否则，输出 "YES" 并给出任意一种可行的划分方式。具体输出格式见下文。 你需要回答 $q$ 个独立的询问。

第一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示询问的数量。接下来有 $q$ 组询问。 每组询问的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$），分别表示数组的长度和需要划分的子段数。 每组询问的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。 保证所有询问中 $n$ 的总和不超过 $2 \cdot 10^5$（即 $\sum n \le 2 \cdot 10^5$）。

对于每个询问，输出一行答案。如果无法将初始数组划分为恰好 $k$ 个子段，并且每个子段的元素和都是奇数，输出一行 "NO"。 否则，输出一行 "YES"，并在第二行输出任意一种可行的划分方式。划分方式可以表示为 $k$ 个整数 $r_1, r_2, \dots, r_k$，满足 $1 \le r_1 < r_2 < \dots < r_k = n$，其中 $r_j$ 表示第 $j$ 个子段的右端点（即属于该子段的最后一个元素的下标），因此数组被划分为 $[1, r_1], [r_1 + 1, r_2], [r_2 + 1, r_3], \dots, [r_{k-1} + 1, n]$。注意 $r_k$ 总是 $n$，但你仍需输出它。

由 ChatGPT 4.1 翻译