概要

区間 \([L_j, R_j]\) に同じ量の水を \(M\) 回加える操作をまとめて処理し、最終的に各花が受け取った総水量が \(S_i\) を超えるかを数えます。

考察

各水やり作業では、ある連続区間のすべての花に同じ水量 \(W_j\) を加えます。
素朴に「作業ごとに区間内の全ての花へ加算」をすると、最悪で \(N \times M \approx 4 \times 10^{10}\) 回の更新が必要になり、確実に時間切れになります。

ここで重要な気づきは、「区間加算をそのまま配列に反映するのではなく、差分（増減の境界）だけを記録すればよい」ということです。

例えば \(N=5\) で、区間 \([2,4]\) に \(+3\) を加える操作を考えます。
各要素を直接更新する代わりに、

• 位置 2 から加算が始まる（ここで \(+3\)）
• 位置 5 (= 4 の次) から加算が終わる（ここで \(-3\)）

という「境界」だけを覚えておき、最後に左から累積和を取れば、各位置の最終加算量が復元できます。
この方法は「いもす法（差分配列）」としてよく使われます。

アルゴリズム

1. 長さ \(N\) の差分配列 diff を用意する（実装では境界処理を楽にするため \(N+1\) サイズ）。
2. 各水やり操作 \((L, R, W)\)（1-indexed, 両端含む）について、
   • diff[L-1] += W（0-indexed に直して、開始位置で増やす）
   • diff[R] -= W（終了位置の次で減らす。ただし \(R=N\) のときは配列外になるので省略）
3. 左から diff の累積和 cur を取り、各花 \(i\) の総水量 cur が \(S_i\) を超えていれば答えに加算する。

このとき累積和 cur は「その花が受け取った総水量（全操作の合計）」になります。

計算量

• 時間計算量: \(O(N + M)\)
  （各操作を \(O(1)\) で差分に反映し、最後に \(N\) 回の累積和）
• 空間計算量: \(O(N)\)
  （差分配列を保持）

実装のポイント

• 入力は \(1\)-indexed なので、開始位置だけ L -= 1 して \(0\)-indexed に直しています。

• 区間 \([L, R]\)（両端含む）への加算は、差分配列では「開始に \(+W\)、終了の次に \(-W\)」です。
  本コードでは diff[R] -= W を行いますが、\(R=N\) のとき diff[N] は実質不要なので if R < N: で分岐しています。

• 水量や必要水分量は最大 \(10^9\)、回数も最大 \(2\times 10^5\) なので累積は最大 \(2\times 10^{14}\) 程度になり得ますが、Python の int なら安全に扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    diff = [0] * (N + 1)

    for _ in range(M):
        L, R, W = map(int, input().split())
        L -= 1
        diff[L] += W
        if R < N:
            diff[R] -= W

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

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。