差分

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

constexpr int inf = 1e9;

int a[5000005],d[5000005];

int main(){
    int n,q,x;
    cin >> n >> q;
    for(int i = 0;i < n;i ++){
        cin >> a[i];
        d[i] = a[i] - a[i - 1];
    }
    for(int i = 0;i < q;i ++){
        int x,y,z;
        cin >> x >> y >> z;
        d[x - 1] += z;
        d[y] -= z;
    }
    int ans = inf;
    int tmp;
    for(int i = 0;i < n;i ++){
        tmp += d[i];
        ans = min(tmp,ans);
    }
    cout << ans;
    return 0;
}