概要

各商品の「合計割引額」を高速に求め、\(W_i\) 以下まで下がる（= 合計割引額が \(W_i\) 以上）商品数を数えます。

考察

クーポン \(j\) は区間 \([L_j, R_j]\) のすべての商品に対して \(D_j\) 円引きをします。すべて適用後、商品 \(i\) の最終価格は
[ \max(0,\; W_i - (\text{商品 }i\text{ にかかる割引額の合計})) ] です。

したがって価格が \(0\) 円になる条件は、 [ \text{割引額の合計} \ge W_i ] となります。最終価格そのものをシミュレーションする必要はなく、各商品にかかる割引額の合計だけ分かればよいのが重要な気づきです。

素朴な方法がダメな理由

各クーポンごとに区間 \([L_j, R_j]\) を全部更新すると、最悪で - クーポン \(Q=2\times 10^5\) - 区間長が最大 \(N=2\times 10^5\)

となり、更新回数が \(O(NQ)\)（約 \(4\times 10^{10}\)）で到底間に合いません（TLE）。

解決策

「区間に一様に足す」操作は、差分配列（いもす法）でまとめて処理できます。
各区間加算を端点だけの更新に変換し、最後に累積和を取れば各要素の合計割引額が \(O(N+Q)\) で求まります。

アルゴリズム

差分配列 diff（長さ \(N\)）を用意して、各クーポン \((L, R, D)\) を次のように処理します（以下は 0-index）：

1. diff[L] += D
2. diff[R+1] -= D（ただし \(R+1 < N\) のときのみ）

こうしておくと、diff の累積和 cur を左から計算したとき、 - cur がその位置にかかる 割引額の合計 になります。

最後に各商品 \(i\) について - cur >= W[i] なら最終価格は \(0\) 円 なので、条件を満たす個数を数えて出力します。

具体例

\(N=5\)、クーポンが \([2,4]\) に \(+3\)（1-index）だとすると（0-index では \([1,3]\)）、 - diff[1] += 3 - diff[4] -= 3 となり、累積和は位置 1〜3 だけ +3 されます。複数クーポンも同様に重ね合わせできます。

計算量

• 時間計算量: \(O(N+Q)\)（クーポン処理が \(O(Q)\)、累積和と判定が \(O(N)\)）
• 空間計算量: \(O(N)\)（差分配列など）

実装のポイント

• 入力は \(2\times 10^5\) 規模なので、sys.stdin.buffer.read() で一括読み込みすると高速です。

• L, R は入力が 1-index なので、コードでは -1 して 0-index に直しています。

• diff[R+1] の更新は、範囲外アクセスを避けるため R+1 < N のときだけ行います。

• 価格が \(0\) 未満にならない条件は、判定を cur >= W[i] とするだけで十分です（実際の最終価格を計算する必要はありません）。

  ソースコード

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    Q = next(it)
    W = [next(it) for _ in range(N)]

    diff = [0] * (N + 1)
    for _ in range(Q):
        L = next(it) - 1
        R = next(it) - 1
        D = next(it)
        diff[L] += D
        if R + 1 < N:
            diff[R + 1] -= D

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

    print(ans)

if __name__ == "__main__":
    main()

---

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