← 返回题目列表

Codeforces · 1807/D

D. 奇怪的查询

中文机器翻译题面 查看原题

你有一个数组 $$$a_1, a_2, \dots, a_n$$$。回答以下形式的 $$$q$$$ 查询:

- 如果我们将数组 $$$a_l, a_{l+1}, \dots, a_r$$$ 范围内的所有元素更改为 $$$k$$$,整个数组的总和会是奇数吗?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行由 $$$2$$$ 整数 $$$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$$$ 行由 $$$3$$$ 整数 $$$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”将被识别为肯定响应。

示例

输入 #1

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

输出 #1

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$$$,这是偶数,因此答案为“否”。
- 如果 $$$(2, 4)$$$ 范围内的元素设置为 $$$3$$$,则数组将变为 $$$\{2, 3, 3, 3, 2\}$$$,总和将为 $$$2+3+3+3+2 = 13$$$,这是奇数,因此答案为“YES”。