概要

\(N\) 個の商品があり、それぞれに複数の区間クーポンによる割引が適用されます。最終的に価格が \(0\) 円になった商品の個数を求めます。

考察

各クーポンは、ある区間 \([L_j, R_j]\) のすべての商品に対して \(D_j\) 円の割引を適用します。
素朴な方法では、クーポンごとに区間内のすべての商品の値引き額を直接加算すると、最悪の場合 \(O(Q \times N)\) かかり、制約が大きいためTLEになります。

重要な観察は、「区間に対する一様な加算処理」が頻繁に行われる点です。このような操作は、いもす法や差分更新のテクニックを使うことで効率的に処理できます。
具体的には、区間 \([L, R]\) に \(D\) を加える操作を、差分配列 diff を使って以下のように表現します：

• diff[L] += D
• diff[R+1] -= D

この操作をすべて行ったあと、diff の累積和を取ることで各要素に適用された合計の値引き額を得ることができます。

最終的な価格は \(\max(0, W_i - \text{discount}_i)\) であり、これが \(0\) になるのは \(W_i \leq \text{discount}_i\) のときです。これを満たす商品の数を数えれば答えになります。

アルゴリズム

1. 差分配列 diff をサイズ \(N+1\) で準備する。
2. 各クーポン \((L, R, D)\) について：
   • diff[L] += D
   • diff[R+1] -= D
3. diff の累積和を計算し、各商品に適用される合計割引額を得る。
4. 各商品 \(i\) について、\(W_i \leq \text{discount}_i\) ならカウントアップ。
5. カウント結果を出力。

計算量

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

実装のポイント

• クーポンの区間は1-indexedで与えられるので、内部処理では0-indexedに変換する必要がある。
• 差分配列のサイズは \(N+1\) にしておくことで、R+1 が範囲外参照にならないようにする。
• 最終的な価格が負にならないように、比較時には \(\max(0, W_i - \text{discount}_i) = 0\) となる条件で判定する。

## ソースコード

```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
    Q = int(data[idx])
    idx += 1
    
    W = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    # クーポン情報を読み取る
    coupons = []
    for _ in range(Q):
        L = int(data[idx]) - 1  # 0-indexed
        idx += 1
        R = int(data[idx]) - 1
        idx += 1
        D = int(data[idx])
        idx += 1
        coupons.append((L, R, D))
    
    # 遅延評価セグメント木を用いて効率的に処理する
    # 各要素は価格から引かれる合計ディスカウント
    # 最終的な価格 = max(0, W[i] - total_discount[i])
    # したがって、total_discount[i] >= W[i] なら価格は0になる
    
    # 区間加算と区間取得ができるデータ構造が必要
    # ここでは、差分更新＋累積和で対応する
    
    # 差分配列を用意して区間[L,R]にDを足す操作を行う
    diff = [0] * (N + 1)
    for L, R, D in coupons:
        diff[L] += D
        if R + 1 < N:
            diff[R + 1] -= D
    
    # 累積和で各商品にかかる合計ディスカウントを計算
    discounts = list(accumulate(diff[:-1]))
    
    count = 0
    for i in range(N):
        if W[i] <= discounts[i]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

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