概要

各区間に水やりを行うクエリが複数与えられ、各花について合計の水量が閾値を超えるかどうかを判定する問題。

考察

この問題では、最大で \(2 \times 10^5\) 個の花と同数の水やり操作が存在するため、単純に各クエリごとに区間に対して水量を加算していると、最悪ケースで \(O(NM)\) の計算量となり、時間制限に間に合わない（TLE）。

そこで、区間に対する一様な加算処理を効率的に行う方法として「差分配列（いもす法）」が有効です。差分配列を使うことで、区間 \([L, R]\) に \(W\) の値を加算する操作を \(O(1)\) で行え、最後に累積和を取ることで各要素の実際の値を得ることができます。

具体的には、配列 diff をサイズ \(N+1\) で準備し、区間 \([L, R]\) に \(W\) を加えるときは

diff[L] += W
diff[R+1] -= W

とします。その後、diff の累積和を取ると、各花に与えられた実際の水量が得られます。

最後に、各花について「与えた水量」が「必要水分量 \(S_i\)」を超えているかを確認し、超えていた株数をカウントすれば答えになります。

アルゴリズム

1. 入力を高速に読み込み、花の必要水分量 \(S_i\) と水やりクエリを取得。
2. 差分配列 diff をサイズ \(N+1\) で初期化。
3. 各水やりクエリ \(L_j, R_j, W_j\) に対して：
   • 0-indexedに変換した上で、diff[L] += W, diff[R+1] -= W を行う。
4. diff の累積和を計算し、各花に与えられた実際の水量 water[i] を求める。
5. 各花について water[i] > S[i] ならカウントアップ。
6. カウント結果を出力。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 区間の添字を1-indexedから0-indexedへ正しく変換すること（\(L_j\), \(R_j\) をそれぞれ -1 する）。
• 差分配列のサイズは \(N+1\) とし、範囲外アクセスを防ぐ。
• 最後の累積和は itertools.accumulate を使うと簡潔に記述できる。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    S = [0] * N
    for i in range(N):
        S[i] = int(data[idx])
        idx += 1
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        W = int(data[idx])
        idx += 1
        
        # 1-indexed -> 0-indexed
        L -= 1
        R -= 1
        
        diff[L] += W
        diff[R + 1] -= W
    
    # 累積和で実際の水量を計算
    water = list(accumulate(diff[:-1]))
    
    # 根腐れをカウント
    count = 0
    for i in range(N):
        if water[i] > S[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。