概要

\(N\) 株の花に対して \(M\) 回の区間への水やりを行い、受けた水の総量が必要水分量を超えた花の数を数える問題です。区間加算を効率的に処理するために「差分配列（いもす法）」を使用します。

考察

素朴なアプローチの問題点

各水やり作業 \(j\) で、位置 \(L_j\) から \(R_j\) までのすべての花に水量 \(W_j\) を加算する方法を考えます。

for 各作業 j:
    for i = L_j to R_j:
        water[i] += W_j

この方法では、1回の水やりで最大 \(O(N)\) の処理が必要です。\(M\) 回の作業があるので、全体で \(O(NM)\) となります。\(N, M \leq 2 \times 10^5\) のとき、最悪 \(4 \times 10^{10}\) 回の演算が必要となり、TLE（時間制限超過） になります。

解決策：差分配列（いもす法）

区間 \([L, R]\) への一様な加算を効率化するテクニックとして「差分配列」を使います。

基本的なアイデア： - 区間 \([L, R]\) に値 \(W\) を加算したいとき、差分配列 diff に対して： - diff[L] += W（区間の開始点で \(+W\)） - diff[R+1] -= W（区間の終了点の次で \(-W\)） - 最後に diff の累積和を取ると、各位置の実際の値が得られる

具体例

\(N = 5\) の花に対して、区間 \([2, 4]\) に水量 \(3\) を加算する場合：

初期: diff = [0, 0, 0, 0, 0, 0]  (サイズ N+1)

操作: diff[2-1] += 3, diff[4] -= 3
      diff = [0, 3, 0, 0, -3, 0]  (0-indexed)

累積和を取る:
      water = [0, 3, 3, 3, 0, ...]
      → 花2, 3, 4 に水量3が加算された状態

アルゴリズム

1. サイズ \(N+1\) の差分配列 diff を \(0\) で初期化
2. 各水やり作業 \((L_j, R_j, W_j)\) に対して：
   • diff[L_j - 1] += W_j（0-indexedに変換）
   • diff[R_j] -= W_j
3. diff の累積和を取りながら、各花 \(i\) が受けた水の総量 water を計算
4. water > S[i] となる花の数をカウント

diff配列のイメージ（1-indexed → 0-indexed変換後）:

位置:    0    1    2    3    4    5   (N=5の場合)
diff:  [+W]  [ ]  [ ]  [ ] [-W]  [ ]  ← 区間[1,4]に加算
        ↓    ↓    ↓    ↓    ↓
累積:   W    W    W    W    0    0    ← 実際の水量

計算量

• 時間計算量: \(O(N + M)\)
  • 差分配列への加算: 各作業 \(O(1)\) × \(M\) 回 = \(O(M)\)
  • 累積和の計算とカウント: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列 diff のサイズ

実装のポイント

1. インデックスの変換: 問題は1-indexedですが、配列は0-indexedなので、L-1 と R を使います（R は R+1-1 で結果的にそのまま）

2. 差分配列のサイズ: diff[R] でアクセスするため、サイズを \(N+1\) にしておく必要があります

3. オーバーフロー対策: 水量の総和は最大 \(M \times 10^9 = 2 \times 10^{14}\) になり得ますが、Pythonでは整数オーバーフローの心配は不要です

4. 累積和とカウントの同時処理: 別々の配列を作らず、ループ内で累積和を計算しながらカウントすることでメモリを節約できます

   ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    
    # 差分配列を使用して区間加算を効率的に処理
    # diff[i] は位置iでの水量の変化量
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L, R, W = map(int, input().split())
        # 1-indexedなので、L-1とRを使う
        diff[L - 1] += W
        diff[R] -= W
    
    # 累積和を取って各花が受けた水の総量を計算
    count = 0
    water = 0
    for i in range(N):
        water += diff[i]
        if water > S[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。