Codeforces Round 859 (Div. 4) D. Odd Queries
给一个长为 \(n\) 的数组 \(a\) 。回到 \(q\) 个询问。
- 让 \(a_l, a_{l + 1}, \cdots, a_r\) 变为 \(k\) ，\(\sum_{i = 1}^r a_i\) 是否为奇数。
每个询问独立。
显然每个学问独立可以使用前缀和计算区间和，单个询问中 \(pre_{1, l - 1} + pre_{r + 1, n} + (r - l + 1) \times k\) 即 \(sum_{i = 1}^r a_i\) 。
(即使不独立，也只是裸的线段树问题。)
#include <bits/stdc++.h>
void solve() {
int n, q; std::cin >> n >> q;
std::vector<long long> a(n+2);
for (int i = 1; i <= n; i++) std::cin >> a[i], a[i] += a[i-1];
for (int i = 0; i < q; i++) {
int l, r, k; std::cin >> l >> r >> k;
std::cout << ( (a[l - 1] - a[0] + 1LL * (r - l + 1) * k + a[n] - a[r]) & 1 ? "YES" : "NO") << '\n';
}
}
int main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}