概要

\(N\) 人の顧客に対して \(Q\) 回の区間加算を行い、最終的にポイントが閾値以上になった顧客の数を数える問題です。差分配列（いもす法）を使って効率的に区間加算を処理します。

考察

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

単純に考えると、各キャンペーン \(j\) で区間 \([L_j, R_j]\) の全顧客のポイントを1つずつ増やす方法があります。

for j in range(Q):
    for i in range(L[j], R[j] + 1):
        A[i] += X[j]

しかし、この方法では1回のキャンペーンで最大 \(N\) 人の顧客を更新する必要があり、全体で \(O(NQ)\) の計算量となります。\(N, Q \leq 2 \times 10^5\) なので、最悪 \(4 \times 10^{10}\) 回の操作が必要となり、TLE（時間制限超過）になってしまいます。

重要な気づき

キャンペーンの順序は最終結果に影響しません。各顧客が最終的に受け取る追加ポイントの合計さえ分かれば良いのです。

例えば、顧客3が以下のキャンペーンの対象だったとします： - キャンペーン1: +5 - キャンペーン3: +3

このとき、顧客3の追加ポイントは \(5 + 3 = 8\) です。

アルゴリズム

差分配列（いもす法） を使います。これは区間加算を \(O(1)\) で記録し、最後にまとめて \(O(N)\) で各要素の値を復元する手法です。

差分配列の仕組み

1. 差分配列 diff を用意: 区間 \([L, R]\) に \(X\) を加算する操作を以下のように記録

   • diff[L] += X（区間の開始位置で \(+X\)）
   • diff[R+1] -= X（区間の終了位置の次で \(-X\)）

2. 累積和で復元: diff の累積和を取ると、各位置への加算値が得られる

具体例

\(N = 5\) で、区間 \([2, 4]\) に \(+10\) する場合：

diff = [0, 0, 0, 0, 0, 0, 0]  # インデックス0〜6
           ↓
diff = [0, 0, 10, 0, 0, -10, 0]  # diff[2] += 10, diff[5] -= 10

累積和を取ると:
add = [0, 0, 10, 10, 10, 0, ...]
          ↑   ↑   ↑
       顧客2,3,4に+10が加算される

全体の流れ

1. 全キャンペーンを差分配列に記録: \(O(Q)\)
2. 累積和を取って各顧客への加算値を計算: \(O(N)\)
3. 各顧客について「初期ポイント + 加算値 ≥ 閾値」を判定してカウント: \(O(N)\)

計算量

• 時間計算量: \(O(N + Q)\)
  • 顧客情報の読み込み: \(O(N)\)
  • キャンペーンの記録: \(O(Q)\)
  • 累積和の計算と判定: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列 A, T, diff, add がそれぞれ \(O(N)\)

実装のポイント

• 差分配列のサイズは \(N + 2\) 以上必要（diff[R+1] でアクセスするため、\(R = N\) のとき diff[N+1] にアクセスする）

• 1-indexed で実装すると問題文の記述と一致して分かりやすい

• ポイントの値が \(10^9\) 単位で、最大 \(Q\) 回加算されるため、合計値は最大で約 \(2 \times 10^{14}\) になる。Pythonでは整数オーバーフローの心配はないが、他の言語では64bit整数型を使う必要がある

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    
    A = [0] * (N + 1)
    T = [0] * (N + 1)
    
    for i in range(1, N + 1):
        a, t = map(int, input().split())
        A[i] = a
        T[i] = t
    
    # 差分配列を使って区間加算を効率的に処理
    diff = [0] * (N + 2)
    
    for _ in range(Q):
        L, R, X = map(int, input().split())
        diff[L] += X
        diff[R + 1] -= X
    
    # 累積和を取って各顧客への加算値を求める
    add = [0] * (N + 1)
    current = 0
    for i in range(1, N + 1):
        current += diff[i]
        add[i] = current
    
    # 参加を決定した顧客の数をカウント
    count = 0
    for i in range(1, N + 1):
        if A[i] + add[i] >= T[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

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