题解

#include <iostream>
#include <vector>
#include <climits>  // 用于INT_MAX
using namespace std;

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);             // 解绑cin和cout
    
    int n, p;
    cin >> n >> p;
    
    vector<int> a(n+2, 0);  // 1-based索引，多开2个位置避免越界
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    // 初始化差分数组
    vector<int> diff(n+2, 0);  // diff[i]表示a[i]与a[i-1]的差
    
    // 处理p次区间操作
    for (int i = 0; i < p; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        // 区间[x,y]加z，转换为差分数组的两次操作
        diff[x] += z;
        diff[y+1] -= z;
    }
    
    // 计算最终分数并找出最小值
    int min_score = INT_MAX;
    int current_add = 0;  // 当前累计加分
    for (int i = 1; i <= n; ++i) {
        current_add += diff[i];  // 计算到第i个位置的总加分
        int final_score = a[i] + current_add;  // 最终分数
        if (final_score < min_score) {
            min_score = final_score;
        }
    }
    
    cout << min_score << endl;
    
    return 0;
}

问题分析与核心思路
问题本质拆解
这是一个典型的区间更新+单点查询问题，需要高效处理p次区间加分操作，最后找出全班最低分。

关键观察
时间复杂度要求：n和p最大为10⁴，暴力解法O(pn)会导致10⁸次操作，接近时间限制边缘
差分算法优势：可以将区间更新操作降为O(1)，最后通过前缀和计算得到最终分数，总时间复杂度O(n+p)
数据范围：初始分数≤100，每次加分≤100，最多10⁴次操作，最终分数≤100+10⁴100=1,001,000，使用int完全足够
最低分查找：可以在计算最终分数的同时直接找出最小值，不需要额外遍历

代码详细解释
差分算法原理
核心思想：将区间更新转换为单点更新，通过前缀和得到最终结果 对区间[x,y]加z，等价于：

diff[x] += z 表示从x开始，所有元素都加z
diff[y+1] -= z 表示从y+1开始，抵消前面的加z操作