Build a pipeline of summaries
Combine initial values, offline additions, coverage conditions, and final queries.
Choose one model for the initial array
Model A initializes differences from the whole starting array, applies markers, and reconstructs final values directly. Model B leaves the original array intact and starts a zero difference table containing only added amounts; final value = original + reconstructed addition.
Both are correct, but do not mix them. If differences already include the original array, adding a[i] again doubles the initial values. Use long long for initial values, deltas, markers, running additions, and final totals; separately bound the sum of all updated values.
Updates first, queries afterward
When every query asks about the final array after all additions, record differences, reconstruct the final values, and build their prefix sums. Reconstruction and prefix construction can share one loop. The result takes O(n + u + q) time and O(n) storage.
This is an offline update phase followed by static queries. It cannot answer a query that must observe an intermediate state by simply including later updates. Preserve the statement’s timeline. The source uses |delta| ≤ 10⁶ here so a conservative total bound of 4.02 × 10¹⁶ fits long long.
// Complete C++23 program. Input: n u q, n initial values,
// then u inclusive l r delta updates, then q inclusive l r queries.
// n,u,q <= 200000; |initial| <= 1e9; |delta| <= 1e6.
#include <iostream>
#include <vector>
int main() {
int n, u, q;
std::cin >> n >> u >> q;
std::vector<long long> a(n + 1, 0), diff(n + 2, 0), pref(n + 1, 0);
for (int i = 1; i <= n; ++i) std::cin >> a[i];
for (int j = 0; j < u; ++j) {
int l, r;
long long delta;
std::cin >> l >> r >> delta;
diff[l] += delta;
diff[r + 1] -= delta;
}
long long added = 0;
for (int i = 1; i <= n; ++i) {
added += diff[i];
pref[i] = pref[i - 1] + a[i] + added;
}
while (q--) {
int l, r;
std::cin >> l >> r;
std::cout << pref[r] - pref[l - 1] << '\n';
}
}Intervals can represent coverage
Each activity on inclusive integer slots [l, r] contributes +1 at l and −1 at r + 1. Reconstruction gives the number of covering intervals at each slot. Shared endpoints count twice: [1,3] and [3,5] both cover slot 3.
Do not transfer this formula silently to continuous half-open time intervals [l, r), whose stop boundary is r and length is r − l. Inclusive integer slots have length r − l + 1. For no intervals, all coverage is zero; threshold zero would qualify all slots if that threshold is permitted.
Prefix the answer predicate, not raw coverage
For many queries asking how many slots have coverage at least a fixed k, reconstruct coverage, transform each slot into (coverage ≥ k), then build a prefix of those 0/1 indicators. Subtract this good-prefix array to answer each requested interval.
Coverage [2, 2, 0] has two slots meeting k = 2, although its raw coverage sum is four. The desired meaning determines what is prefixed. If every query has a different threshold, one good-prefix array built for a single k is insufficient.
Difference array
Start with eight zeroes. Add to an inclusive range using d[l] += v and d[r + 1] -= v. The last cell is a sentinel.
Difference array (index 8 is the sentinel)
Values after accumulation
No updates yet. Choose a range, then apply an addition.
Guided simulation · Change the inputs to test your understanding.
Coverage is [1, 2, 2, 1, 2, 1]. For fixed k = 2, how many qualifying slots are in [3, 5]?
Turn the idea into code
Start with [4, −2, 7, 0, 3]. Add 3 to [2,4] and −1 to [1,2]. Give the final array and its sums for [1,5], [2,4], and [1,1].
Give me a hint
Reconstruct added amounts first, then combine them with the original values before building prefixes.
Show the explained solution
Added amounts are [−1, 2, 3, 3, 0]. Final values are [3, 0, 10, 3, 3]. The queried sums are 19, 13, and 3. These answers assume both updates have already happened.
Your notes
Mark complete when you can explain it yourself.