题解
由于每次操作都是基于原始数组，且只需要判断总和的奇偶性，因此不必真正修改数组。
1. 预处理
首先计算原始数组的总和：
S=∑i=1nai
P3580.第2题-原始数组判断
题目内容
给定一个长度为n 的整数数组{a1,a2,...,an}。有q次独立询问，每次给出一个区间[l,r]与一个整数k。在本次询问中，将al,al+1,...,ar 改写为一个交替序列:
- 对所有j∈[l,r]，若j−l为偶数，则令aj=k；若j−l为奇数，则令aj=k+1。
所有询问相互独立，均基于原始数组判断。请回答改写后整个数组元素之和是否为奇数。若为奇数输出YES，否则输出NO
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数t(1≦t≦104)表示测试用例数量。
对每组测试用例:
-
第一行输入两个整数n,q(1≦n≦2×105;1≦q≦2×105);
-
第二行输入n个整数a1,a2,...,an(1≦ai≦109)
此后q行，每行输入三个整数l,r,k(1≦l≦r≦n;0≦k≦109)。
除此之外，保证单个测试文件的n之和不超过2×105，q之和不超过2×105。
输出描述
对于每次询问，新起一行输出一个字符串:若改写后整个数组之和为奇数，输出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；其余两次询问同理。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
