区间更新与差分数组：高效求解最大干净度

```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> area(n + 2, 0); for (int i = 0; i < q; i++) { int L, R, x; cin >> L >> R >> x; area[L] += x; area[R + 1] -= x; } int maxClean = 0; int current = 0; for (int i = 1; i <= n; i++) { current += area[i]; maxClean = max(maxClean, current); } cout << maxClean << endl; return 0; } ``` 📝 **算法解析** - 使用差分数组优化区间更新操作。 - 每次打扫操作 `[L, R]` 增加 `x`，只需在 `area[L]` 加 `x`，在 `area[R+1]` 减 `x`。 - 通过前缀和还原每个区域的最终干净度。 - 遍历过程中记录最大值。 ⚙️ **复杂度分析** - 时间复杂度：O(n + q)，高效处理大规模数据。 - 空间复杂度：O(n)，仅使用差分数组。 🔧 **示例输入** ``` 5 3 1 3 2 2 5 1 3 4 3 ``` **示例输出** ``` 6 ``` ######[AI问答 | 336点数解答 | 2026-03-20 21:57:13]