差分数组，轻松求解连续区域最大干净度

这是一个典型的**差分数组 + 前缀和**问题。 因为 n 最大为 99，q 也没有明确上限但根据数据范围可以允许 q 较大，直接模拟区间加会超时（O(n*q)），使用差分可以优化到 **O(n+q)**。 ### 🧠 解题思路 1. **差分数组**： - 每次对区间 [Li, Ri] 加 xi 时，在位置 Li 加上 xi，在位置 Ri+1 减去 xi。 - 最后对整个数组做一次前缀和，就得到每个区域最终的干净度。 2. **找最大值**： - 遍历一遍前缀和结果，记录最大值。 ### 📝 代码实现（C++） ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; // 差分数组，长度为 n+2 防止越界 vector<int> diff(n + 2, 0); for (int i = 0; i < q; i++) { int L, R, X; cin >> L >> R >> X; diff[L] += X; diff[R + 1] -= X; } int current = 0; int maxClean = 0; for (int i = 1; i <= n; i++) { current += diff[i]; if (current > maxClean) { maxClean = current; } } cout << maxClean << endl; return 0; } ``` ### 🧪 样例验证 输入： ``` 5 4 1 3 1 2 4 1 3 5 1 5 5 1 ``` 差分过程： - 初始 diff: `[0,0,0,0,0,0,0]` - 第1次: diff[1]+=1, diff[4]-=1 → diff: `[0,1,0,0,-1,0,0]` - 第2次: diff[2]+=1, diff[5]-=1 → diff: `[0,1,1,0,-1,-1,0]` - 第3次: diff[3]+=1, diff[6]-=1 → diff: `[0,1,1,1,-1,-1,-1]` - 第4次: diff[5]+=1, diff[6]-=1 → diff: `[0,1,1,1,-1,0,-2]` 前缀和： - i=1: 1 - i=2: 2 - i=3: 3 - i=4: 2 - i=5: 2 最大值：3 ✅ ######[AI问答 | 632点数解答 | 2026-06-06 14:38:20]