题解

由于每次操作都是基于原始数组，且只需要判断总和的奇偶性，因此不必真正修改数组。

1. 预处理

首先计算原始数组的总和：

$S = \sum_{i=1}^{n} a_i$

题目内容

给定一个长度为n 的整数数组{$a_1,a_2,...,a_n$}。有$q$次独立询问，每次给出一个区间$[l,r]$与一个整数$k$。在本次询问中，将$a_l,a_{l+1},...,a_r$ 改写为一个交替序列:

• 对所有$j∈[l,r]$，若$j-l$为偶数，则令$a_j=k$；若$j-l$为奇数，则令$a_j=k+1$。

所有询问相互独立，均基于原始数组判断。请回答改写后整个数组元素之和是否为奇数。若为奇数输出$YES$，否则输出$NO$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$t (1 ≦t≦10^4)$表示测试用例数量。

对每组测试用例:

• 第一行输入两个整数$n,q(1≦n≦2×10^5;1≦q≦2×10^5)$;

• 第二行输入$n$个整数$a_1,a_2,...,a_n (1≦a_i≦10^9)$

此后$q$行，每行输入三个整数$l,r,k (1≦l≦r≦n;0≦k≦10^9)$。

除此之外，保证单个测试文件的$n$之和不超过$2×10^5$，$q$之和不超过$2×10^5$。

输出描述

对于每次询问，新起一行输出一个字符串:若改写后整个数组之和为奇数，输出$YES$；否则输出$NO$。

样例1

输入

2
5 4
1 2 3 4 5
1 3 2
2 5 1
1 5 10
3 3 0
3 3
1 1 1
1 3 0
2 2 5
1 1 2

输出

NO
YES
NO
NO
YES
YES
NO

说明

在第一组测试数据中:

• 对于询问$(l,r,k)=(1,3,2)$，将区间改写为{$2,3,2$}，全局和变为偶数，输出$NO$；

• 对于询问$(2,5,1)$，将区间改写为{$1,2,1,2$}，全局和为奇数，输出$YES$；其余两次询问同理。