概要

区間加算（キャンペーン）をすべて反映したあとの各顧客の旅行ポイントを求め、最終的に閾値 \(T_i\) 以上になった人数を数える問題です。

考察

各キャンペーンは「区間 \([L_j, R_j]\) の全員に \(X_j\) を加算する」という操作です。
これを素朴に実装して、毎回区間内の全員に加算すると、最悪で

• 1回のキャンペーンで \(O(N)\) 更新
• キャンペーンが \(Q\) 回

となり、合計 \(O(NQ)\)（最大で \(4\times 10^{10}\) 程度）になってしまい、時間切れ（TLE）になります。

ここで重要な観察は次の通りです：

• 区間加算の結果として「各位置（各顧客）が合計でいくら加算されるか」だけ分かればよい
• 区間加算は 差分配列（いもす法） を使うと \(O(1)\) で記録でき、最後に累積和でまとめて復元できる

差分配列の直感（小例）

例えば \(N=5\) で、区間 \([2,4]\) に \(+3\) をしたいとします。
差分配列 diff を用意して

• diff[2] += 3（2番目から増える）
• diff[5] -= 3（4番目の次＝5番目から元に戻す）

と書いておき、diff の累積和を取ると、2〜4番目だけが +3 されている状態を復元できます。

この考え方を全キャンペーンに対して行えば、加算総量を高速に求められます。

アルゴリズム

1. 顧客ごとに初期値 \(A_i\) と閾値 \(T_i\) を読む。
2. 長さ \(N+2\) の差分配列 diff を用意する（添字の都合で余裕を持たせる）。
3. 各キャンペーン \((L, R, X)\) について、次を行う：
   • diff[L] += X
   • diff[R+1] -= X
4. 左から順に累積和 add を更新していく：
   • add += diff[i] が「顧客 \(i\) が最終的に受け取る加算分の合計」
5. 各顧客について \(A_i + add \ge T_i\) なら参加確定としてカウントする。
6. カウントを出力する。

この方法では、区間更新を直接配列に反映せず、「増え始め」と「増え終わり」だけを記録し、最後に一括で復元します。

計算量

• 時間計算量: \(O(N+Q)\)
  （各キャンペーンを \(O(1)\) で記録し、最後に \(O(N)\) で累積和と判定）
• 空間計算量: \(O(N)\)
  （差分配列と入力配列を保持）

実装のポイント

• 入力の \(L, R\) は \(1\) 始まりなので、差分配列も diff[1..N] を主に使う設計にすると実装が楽です（コードもその形）。

• diff[R+1] にアクセスするため、配列長を N+2 にして範囲外アクセスを避けます。

• 最終判定では、顧客配列 A, T は 0-index、累積和は 1-indexでずれが出るため、A[i-1], T[i-1] のように合わせています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    Q = int(next(it))

    A = [0] * N
    T = [0] * N
    for i in range(N):
        A[i] = int(next(it))
        T[i] = int(next(it))

    diff = [0] * (N + 2)
    for _ in range(Q):
        L = int(next(it))
        R = int(next(it))
        X = int(next(it))
        diff[L] += X
        diff[R + 1] -= X

    ans = 0
    add = 0
    for i in range(1, N + 1):
        add += diff[i]
        if A[i - 1] + add >= T[i - 1]:
            ans += 1

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

---

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