区间增量求最大值：差分数组高效解法C++实现

根据您的需求，这是一个典型的区间增量更新后求最大值的问题。可以使用差分数组或线段树解决。这里提供一种简单高效的差分数组解法。 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; vector<long long> diff(n + 2, 0); // 差分数组，多开两个位置防止越界 for (int i = 0; i < q; i++) { int L, R; long long X; cin >> L >> R >> X; // 差分操作：左端点加X，右端点后一个位置减X diff[L] += X; diff[R + 1] -= X; } long long current = 0; long long maxClean = 0; // 前缀和还原每个区域的干净度 for (int i = 1; i <= n; i++) { current += diff[i]; maxClean = max(maxClean, current); } cout << maxClean << endl; return 0; } ``` 算法说明： - 差分数组`diff`可以高效记录区间增量。 - 每次打扫在`diff[L]`加X，在`diff[R+1]`减X。 - 最后遍历一次，累加差分值得到每个区域的最终干净度，同时记录最大值。 - 时间复杂度O(n+q)，空间复杂度O(n)。 ######[AI问答 | 341点数解答 | 2026-08-02 15:41:56]