题目描述

你有一个数组 $a_1, a_2, \dots, a_n$。你需要回答 $q$ 个如下形式的询问：

• 如果我们将数组中区间 $a_l, a_{l+1}, \dots, a_r$ 的所有元素都改为 $k$，那么整个数组的和会是奇数吗？

注意，所有的询问都是独立的，不会影响后续的询问。

输入格式

每组测试数据包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 2 \cdot 10^5$；$1 \le q \le 2 \cdot 10^5$），分别表示数组的长度和询问的数量。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示数组 $a$。

接下来的 $q$ 行，每行包含三个整数 $l, r, k$（$1 \le l \le r \le n$；$1 \le k \le 10^9$），表示一次询问。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$q$ 的总和也不超过 $2 \cdot 10^5$。

输出格式

对于每个询问，如果整个数组的和变为奇数，输出 "YES"；否则输出 "NO"。

你可以以任意大小写输出答案（如 "yEs"、"yes"、"Yes"、"YES" 都会被认为是肯定回答）。

样例

2
5 5
2 2 1 3 2
2 3 3
2 3 4
1 5 5
1 4 9
2 4 3
10 5
1 1 1 1 1 1 1 1 1 1
3 8 13
2 5 10
3 8 10
1 10 2
1 9 100

YES
YES
YES
NO
YES
NO
NO
NO
NO
YES

样例说明

对于第一个测试用例：

• 如果将区间 $(2, 3)$ 的元素都改为 $3$，数组变为 $\{2, 3, 3, 3, 2\}$，和为 $2+3+3+3+2=13$，是奇数，因此答案为 "YES"。
• 如果将区间 $(2, 3)$ 的元素都改为 $4$，数组变为 $\{2, 4, 4, 3, 2\}$，和为 $2+4+4+3+2=15$，是奇数，因此答案为 "YES"。
• 如果将区间 $(1, 5)$ 的元素都改为 $5$，数组变为 $\{5, 5, 5, 5, 5\}$，和为 $5+5+5+5+5=25$，是奇数，因此答案为 "YES"。
• 如果将区间 $(1, 4)$ 的元素都改为 $9$，数组变为 $\{9, 9, 9, 9, 2\}$，和为 $9+9+9+9+2=38$，是偶数，因此答案为 "NO"。
• 如果将区间 $(2, 4)$ 的元素都改为 $3$，数组变为 $\{2, 3, 3, 3, 2\}$，和为 $2+3+3+3+2=13$，是奇数，因此答案为 "YES"。

由 ChatGPT 4.1 翻译

来源

Codeforces 1807D，英文题名 Odd Queries。