この問題は俗にimos法と呼ばれる、累積和の逆操作を用いることで高速に求めることができます。

累積和は数列同士の和を保ちます。つまり、「数列 \(A\) の累積和と数列 \(B\) の累積和を足した数列」は「数列 \(A\) と数列 \(B\) を足した数列の累積和」になります。

                  差分 ←      → 累積和
A   0  1  0  0  1  0  0        0  0  1  1  1  2  2  2 
B   0  0 -1  0  0  2  0        0  0  0 -1 -1 -1  1  1
A+B 0  1 -1  0  1  2  0        0  0  1  0  0  1  3  3

また「ある区間の要素が \(1\) でそれ以外は全て \(0\)」という数列に対し、累積和の逆操作を行うと「\(1\) と \(-1\) が \(1\) 個ずつで他は全て \(0\) 」という数列になります。

    0   1   0   0   0  -1   0   0
            累積和↓   ↑差分
  0   0   1   1   1   1   0   0   0

よって「 \((0,\dots,0,D_i,\dots,D_i,0,\dots,0)\) の形の数列 \(M\) 個の和」は「\((0,\dots,0,D_i,0,\dots,0,-D_i,0,\dots,0)\) の形の数列 \(M\) 個の和の累積和」となり、これは \(O(N+Q)\) で求めることができます。

このように、累積和の逆操作を用いて計算を高速化する手法全般をimos法と呼びます。

実装例 (C++)

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

int main(){
  int n, q;
  cin >> n >> q;
  vector<int>w(n);
  for(int i=0; i<n; i++) cin >> w[i];
  vector<long long>s(n+1);
  for(int i=0; i<q; i++){
    int l, r, d;
    cin >> l >> r >> d;
    s[l-1] += d;
    s[r] -= d;
  }
  for(int i=0; i<n; i++){
    s[i+1] += s[i];
  }

  int ans = 0;
  for(int i=0; i<n; i++){
    if(s[i] >= w[i]){
      ans++;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N, Q = map(int, input().split())
W = list(map(int, input().split()))
S = [0] * (N+1)
for _ in range(Q):
  L, R, D = map(int, input().split())
  S[L-1] += D
  S[R] -= D

for i in range(N):
  S[i+1] += S[i]

ans = 0
for i in range(N):
  if S[i] >= W[i]:
    ans += 1

print(ans)