喵哈囉~ 主人！今天由我，乃爱，来为你讲解 Codeforces 上的这道 D. Odd Queries 题目哦。这道题看起来有点复杂，但只要找到正确的思路，就会变得非常简单，就像找到一团完美的毛线球一样！✨

题目大意

这道题是说呀，我们有一个装满数字的数组 a。然后呢，会有一连串的询问。

每一次询问都会给我们三个数字：l, r 和 k。它会问我们一个“如果”的问题：“如果，我们把数组 a 里面从第 l 个位置到第 r 个位置的所有数字，都换成新的数字 k，那么整个数组所有数字加起来的总和，会是一个奇数吗？”

最关键的一点是，每次询问都是独立的、假设性的，并不会真的改变原来的数组哦。所以每次我们都得从最开始的那个数组出发进行计算，喵~

举个例子： 数组是 {2, 2, 1, 3, 2}。 询问是 l=2, r=3, k=3。 我们就要想象一下，如果把第2个和第3个数字都变成3，数组就成了 {2, 3, 3, 3, 2}。 它们的总和是 2+3+3+3+2 = 13。因为13是奇数，所以我们就要回答 "YES"。

解题思路

如果我们真的按照题目说的，每次询问都去模拟一遍：先复制一个新数组，然后修改 l 到 r 区间的值，最后再把整个新数组从头到尾加一遍……哼哼，那肯定会超时的啦！(｡•ˇ‸ˇ•｡) 那么多询问，每次都遍历一次数组，计算机可受不了这个委屈。

所以，我们需要一种更聪明的办法，喵~

我们真正关心的，其实不是新的总和具体是多少，而仅仅是它的奇偶性。

让我们来分析一下新的总和是怎么构成的：

新总和 = (原来的总和) - (被替换掉的区间 [l, r] 的原始和) + (新填入的数字 k 的总和)

这个公式就是我们解题的核心哦！我们来一项一项看怎么快速得到它们：

1. 原来的总和 (total_sum)：这个很简单，我们可以在读入数组的时候就把它算出来，之后就不用再算了。

2. 新填入的数字 k 的总和：区间 [l, r] 的长度是 r - l + 1。这个区间里所有的数都变成了 k，所以这部分的和就是 (r - l + 1) * k。

3. 被替换掉的区间 [l, r] 的原始和：这个是关键！如果每次都用循环去算 a[l] + a[l+1] + ... + a[r]，那不就又回到慢吞吞的老路上了吗？

这时候，就要请出我们的好朋友——前缀和 (Prefix Sum) 数组啦！✨

前缀和数组 p 是一个神奇的工具。p[i] 里面存的是原始数组 a 从第1个元素到第 i 个元素的总和。 有了它，我们想知道任意区间 [l, r] 的和就易如反掌了，只需要用 p[r] - p[l-1] 就能在 O(1) 的时间复杂度内瞬间得到！

所以，我们的完整策略就是：

1. 预处理：在处理询问之前，先花 O(n) 的时间计算出整个数组的前缀和数组 p。同时，p[n] 就是我们需要的 原来的总和。
2. 处理询问：对于每一个询问 (l, r, k)：
   • 用前缀和数组计算出区间 [l, r] 的原始和：range_sum = p[r] - p[l-1]。
   • 计算出新的总和：new_total_sum = p[n] - range_sum + (r - l + 1) * k。
   • 判断 new_total_sum 的奇偶性。如果 new_total_sum % 2 != 0，它就是奇数，我们就输出 "YES"；否则输出 "NO"。

这样一来，每次询问我们都只需要做几次简单的加减乘除，速度快得像猫咪冲向小鱼干一样！

题解代码

这是用 C++ 实现的代码，乃爱在里面加了一些注释，方便主人理解哦~

#include <iostream>
#include <vector>
#include <numeric>

// 解决单个测试用例的函数，喵~
void solve() {
    int n; // 数组长度
    int q; // 询问次数
    std::cin >> n >> q;

    // p 是前缀和数组。p[i] 存的是前 i 个元素的和。
    // 为了和题目的 l, r (从1开始) 对应，我们使用 1-based 索引会更方便。
    // 和可能会很大，所以要用 long long 哦，不然会溢出的！
    std::vector<long long> p(n + 1, 0LL);
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        p[i + 1] = p[i] + val;
    }

    // 原始数组的总和，就是前缀和数组的最后一个元素啦
    long long total_sum = p[n];

    for (int i = 0; i < q; ++i) {
        int l, r;
        long long k;
        std::cin >> l >> r >> k;

        // 使用前缀和数组，O(1) 时间计算出原数组 [l, r] 区间的和
        long long range_sum = p[r] - p[l - 1];
        
        // [l, r] 区间的元素个数
        long long length = r - l + 1;
        
        // 计算新的总和：
        // 新总和 = (原总和 - 被替换掉的区间的和) + (新数字的和)
        long long new_total_sum = total_sum - range_sum + length * k;

        // 检查新总和的奇偶性
        // 一个数如果是奇数，那它除以 2 的余数就不会是 0
        if (new_total_sum % 2 != 0) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}

int main() {
    // 这两行是为了在处理大量输入输出时跑得更快，是竞赛的小技巧哦
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t; // 测试用例的数量
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题主要用到了一个非常基础但超级有用的算法技巧：

1. 前缀和 (Prefix Sum)

前缀和是一种能极大优化“区间查询”问题的技巧。它的核心思想是用空间换时间。

• 是什么：对于一个数组 a，它的前缀和数组 p 的定义是 p[i] = a[1] + a[2] + ... + a[i]。也就是说，p[i] 存储了原数组从开头到第 i 个位置的所有元素的累加和。通常我们会让 p[0] = 0，这样更方便计算。

• 怎么构建：构建前缀和数组非常简单，只需要一次遍历。递推公式是 p[i] = p[i-1] + a[i]。时间复杂度是 O(n)。

• 怎么用：它的魔力在于，一旦构建完成，查询任意区间 [l, r] 的和就变成了 O(1) 的操作。 sum(l, r) = a[l] + ... + a[r]= (a[1] + ... + a[r]) - (a[1] + ... + a[l-1])= p[r] - p[l-1]

  看，只需要一次减法！是不是超快？

2. 奇偶性 (Parity)

这道题的最终目的是判断奇偶性。虽然我们直接计算了总和再判断，但了解一些奇偶性的运算规则也很有趣哦，喵~

• 奇数 ± 奇数 = 偶数
• 偶数 ± 偶数 = 偶数
• 奇数 ± 偶数 = 奇数
• 奇数 × 奇数 = 奇数
• 奇数 × 偶数 = 偶数
• 偶数 × 偶数 = 偶数

我们可以用这些规则来只关心奇偶性，而不是具体的数值。比如 new_total_sum 的奇偶性，就等于 (total_sum的奇偶性) - (range_sum的奇偶性) + ((length * k)的奇偶性)。不过直接计算总和再取模 2 是最直接、最不容易出错的方法啦！

好啦，这次的讲解就到这里~ 主人有没有完全明白呀？如果有任何问题，随时都可以再来问乃爱哦！(>^ω^<)