概要

\(N\) 個の商品に対して \(Q\) 個の「区間加算（割引）」を行い、最終的な価格が 0 円以下（合計割引額が初期価格以上）になる商品の個数を求める問題です。

考察

素朴な方法

各クーポンについて、指定された範囲 \(L_j\) から \(R_j\) までの商品の価格を一つずつ更新していく方法が考えられます。しかし、この方法では 1 つのクーポンにつき最大 \(N\) 回の操作が必要になり、最悪の場合の計算量は \(O(N \times Q)\) となります。 本問題では \(N, Q \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

効率的なアプローチ

この問題で求められているのは「すべてのクーポンを適用した後の最終的な状態」です。途中の価格を逐一確認する必要がないため、区間への加算を効率的に行う手法が有効です。 各商品 \(i\) について、「最終的な合計割引額が \(W_i\) 以上であるか」を判定すればよいため、いもす法（差分更新）を用いて合計割引額を計算します。

アルゴリズム

いもす法（差分配列）

区間 \([L, R]\) に値 \(D\) を加算する操作は、差分配列 diff を用いることで高速化できます。

1. 長さ \(N+2\) の配列 diff を 0 で初期化します。
2. 各クーポン \((L_j, R_j, D_j)\) について、以下の 2 箇所だけを更新します。
   • diff[L_j] += D_j
   • diff[R_j + 1] -= D_j
3. すべてのクーポンを処理した後、diff の前から順に累積和をとります。
   • \(i\) 番目の商品の合計割引額は \(\sum_{k=1}^{i} diff[k]\) となります。
4. 各商品 \(i\) について、合計割引額 >= W_i であれば、その商品の最終価格は 0 円になります。

この手法を用いることで、各クポーンの処理を \(O(1)\)、最後の集計を \(O(N)\) で行うことができます。

計算量

• 時間計算量: \(O(N + Q)\)
  • クーポンの処理に \(O(Q)\)、累積和の計算と判定に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 商品の価格を保持する配列と、差分配列（いもす法用）に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(Q\) が大きいため、Python では sys.stdin.read().split() などを用いて入力を一括で読み込むと実行時間を短縮できます。

• インデックスの扱い: 問題文は 1-indexed（商品番号 1〜N）ですが、配列は 0-indexed であることが多いです。差分配列の更新時に R_j + 1 にアクセスするため、配列サイズを少し大きめ（\(N+2\) など）に確保しておくと範囲外エラーを防げます。

• 数値の大きさ: 合計割引額や初期価格は \(10^9\) を超えることがありますが、Python は標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 商品の個数 N と クーポンの枚数 Q
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # 各商品の初期価格 W_i (1-indexedを0-indexedとして扱う)
    W = [int(x) for x in input_data[2:2+N]]
    
    # いもす法（差分配列）を用いて各商品に適用される合計割引額を計算します
    # 商品番号は 1 から N なので、サイズ N + 2 の配列を用意します
    diff = [0] * (N + 2)
    
    # クーポンの情報を処理します
    # 各クーポンは L_j から R_j の範囲に D_j の割引を適用します
    idx = 2 + N
    for _ in range(Q):
        l = int(input_data[idx])
        r = int(input_data[idx+1])
        d = int(input_data[idx+2])
        diff[l] += d
        diff[r + 1] -= d
        idx += 3
        
    # 差分配列を累積和することで、各商品の最終的な合計割引額を求めます
    ans = 0
    current_discount = 0
    for i in range(1, N + 1):
        current_discount += diff[i]
        # 商品 i の初期価格は W[i-1]
        # 合計割引額が初期価格以上であれば、最終的な価格は 0 円になります
        if current_discount >= W[i-1]:
            ans += 1
            
    # 結果を出力します
    print(ans)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。