题解 | 【模板】差分

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  我先是用的暴力，没有算时间复杂度，超时了，还不知道差分看的题解，C++第一篇有图片我感觉讲的挺好的
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> a(n);
  vector<ll> b(n);
  cin >> a[0];
  b[0] = a[0];
  for (int i = 1; i < n; i++) {
    cin >> a[i];
    b[i] = a[i] - a[i - 1];//------计算差分，本来最好数组多开一个
  }
  int l, r, k;
  while(m--){
    cin >> l >> r >> k;
    b[l - 1] += k;
    if (r < n) b[r] -= k;
  }
  a[0] = b[0];
  cout << b[0] << ' ';
  for (int i = 1; i < n; i++){
    a[i] = a[i - 1] + b[i];
    cout << a[i] << ' ';
  }
}
// 64 位输出请用 printf("%lld")