文字教学

这道题数据量极大（n≤5e6），直接遍历区间加分会超时，需要用差分法高效处理区间更新：

1. 差分核心思想：对区间 [x,y] 加 z，只需在差分数组 d[x] += z、d[y+1] -= z（若y+1≤n）。
2. 步骤：
   • 初始化差分数组，d[1] = a[1]，d[i] = a[i] - a[i-1]（i>1）；
   • 处理p次区间加分，更新差分数组；
   • 用差分还原最终成绩，同时遍历找最小值。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 5e6 + 10;
ll d[N]; // 差分数组

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, p;
    cin >> n >> p;
    for (int i = 1; i <= n; ++i) cin >> d[i];
    // 构建差分数组
    for (int i = n; i > 1; --i) d[i] -= d[i-1];
    
    // 处理区间加分
    int x, y, z;
    for (int i = 0; i < p; ++i) {
        cin >> x >> y >> z;
        d[x] += z;
        if (y + 1 <= n) d[y+1] -= z;
    }
    
    // 还原数组并找最小值
    ll mn = 1e18, cur = 0;
    for (int i = 1; i <= n; ++i) {
        cur += d[i];
        if (cur < mn) mn = cur;
    }
    cout << mn << endl;
    return 0;
}