D Odd Queries 题解

原题传送门

题意简述

给定一个数组，再给出 m 个各自独立（即这个操作不影响后续的询问）的询问，每次给定一个区间，询问将这个区间每个元素都修改为k后，数组总和会是奇数吗？

解决思路

由于n的范围很大，所以暴力肯定是不可以了，由于每个询问是独立的，我们不需要修改序列，所以不需要使用数据结构。

我们思考后可以发现，其实可以 判断修改后的总和 与 原来这个区间的总和 奇偶性的异同，如果相同其实修改后整个数组的奇偶性是不变的，不同才会发生改变。

讲了那么多，肯定有小伙伴已经懵了，别急，举个例子就懂啦。

例如下面这个数组：

a[5] = {1, 2, 3, 4, 5} 显然，总和为15

------------------------------------分割线qwq

选择区间1 ~ 3 修改为 3

此时修改后的总和： (r - l + 1) * k = (3 - 1 + 1) * 3 = 9
原来的总和： a[1] + a[2] + a[3] = 1 + 2 + 3 = 6
修改后的数组：a[5] = {3, 3, 3, 4, 5} 显然，总和为18

发现了吗，修改后的总和9与原来的总和6奇偶性不同，所以修改后的数组总和奇偶性也与原来不同

------------------------------------又是分割线qwq

选择区间1 ~ 3 修改为 4

此时修改后的总和： (r - l + 1) * k = (3 - 1 + 1) * 4 = 12
原来的总和： a[1] + a[2] + a[3] = 1 + 2 + 3 = 6
修改后的数组：a[5] = {4, 4, 4, 4, 5} 显然，总和为21

发现了吗，修改后的总和12与原来的总和6奇偶性相同，所以修改后的数组总和奇偶性也与原来相同

那有了思路，该如何写代码呢？

其实代码里最难的就是如何在O (n) 的时间复杂度内求出某个数组的和，由于 n 很大，所以不能暴力。

这就要运用到一种新奇的算法 -- 前缀和，关于前缀和在此不进行介绍，需要点这学习。

那代码其实就很简单了，但是要注意下，问题问的是数组总和是否是奇数，所以要特判下。

code:

#include <iostream>
#include <cstring>

#define int long long

const int N = 200010;

using namespace std;

int t;

int s[N];

void solve()

{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) 
	{
		int x;
		cin >> x;
		s[i] = s[i - 1] + x;//前缀和
	}
    bool f = true;
	if (s[n] % 2) f = false;//数组总和奇偶性，false表示奇数，true表示偶数
	while (m -- )
	{
		int l, r, k, sum;
		cin >> l >> r >> k;
		sum = (r - l + 1) * k;//修改后的区间和
		int fir = (sum % 2), second = (s[r] - s[l - 1]) % 2;//两个总和的奇偶性
		if (!f)
		{
			if (fir == second) puts("YES");
			else puts("NO");
		}
		else
		{
			if (fir == second) puts("NO");
			else puts("YES");
		}
	}
}

signed main()

{
	cin >> t;
	while (t -- ) solve();
}