差分

blablabla

(线性) $O(m)$

非常🐂逼

C++ 代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i ++) 
    {
        cin >> a[i];
        b[i] = a[i] - a[i - 1];  //运算差分数组
    }
    for(int i = 1; i <= m; i ++)
    {
        int l, r, c;
        cin >> l >> r >> c;
        b[l] += c;   //b[l]+c通过前缀和的累加效应会让包括c在内后面的项全部+c
        b[r + 1] -= c;   //b[r+1]-c同上会让包括r+1在内后面的项全部-c，这样就实现了r后面的项不改变，和前面的+c抵消了
    }
    for(int i = 1; i <= n; i ++)
    {
        b[i] = b[i] + b[i - 1];   //求差分数组的前缀和，还原出原数组
        cout << b[i] << " ";
    }
    return 0;
}