概要

区間に対する加算クエリを処理した後、各要素が閾値以上かどうかを判定する問題。

考察

この問題では、最大で \(2 \times 10^5\) 個の顧客と同数のキャンペーンがあるため、素朴に各クエリごとに区間に対して加算処理を行うと、最悪計算量が \(O(NQ) = O(4 \times 10^{10})\) となり、明らかに時間内に収まりません。

そこで、「区間への一様加算」を効率的に処理するためにimos法（いもす法）というテクニックを使います。これは、差分配列を用いることで、区間の加算を定数時間で処理し、最後に累積和を取ることで実際の値を得る方法です。

また、最終的な各顧客のポイントは、初期値にキャンペーンによる増加分を足したものになります。この増加分をimos法で高速に求め、最後に判定を行えばよいです。

アルゴリズム

1. 各顧客の初期ポイント \(A_i\) と閾値 \(T_i\) を読み込む。
2. キャンペーンによるポイント増加を記録するために、サイズ \(N+1\) の差分配列 diff を用意する。
3. 各キャンペーン \([L_j, R_j]\) に対して、diff[L_j] += X_j、diff[R_j + 1] -= X_j を行う（1-indexed → 0-indexedに変換）。
4. diff の累積和を求めることで、各顧客のポイント増加量 final_add[i] を求める。
5. 各顧客について、最終ポイント \(A_i + \text{final\_add}[i]\) が \(T_i\) 以上であればカウントアップ。
6. 最終的なカウントを出力。

例

例えば、\(N=3\), 初期ポイント \(A = [10, 20, 30]\), 閾値 \(T = [25, 30, 40]\) とする。

キャンペーン： - 区間 \([1, 2]\) に \(5\) 加算 → 顧客1, 2 が \(+5\) - 区間 \([2, 3]\) に \(10\) 加算 → 顧客2, 3 が \(+10\)

差分配列の操作： - diff[0] += 5, diff[2] -= 5 - diff[1] += 10, diff[3] -= 10

累積和を取ると： - final_add = [5, 15, 10]

最終ポイント： - 顧客1: \(10 + 5 = 15 < 25\) → NG - 顧客2: \(20 + 15 = 35 \geq 30\) → OK - 顧客3: \(30 + 10 = 40 \geq 40\) → OK

答え：2人

計算量

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

実装のポイント

• インデックスは1-indexedから0-indexedに変換すること（\(L-1\), \(R-1\)にする）。
• 差分配列のサイズは \(N+1\) にしておき、範囲外アクセスを防ぐ。
• 最後の累積和は長さ \(N\) 分だけ取り出す（末尾の余分な要素を除く）。

## ソースコード

```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
    
    A = [0] * N
    T = [0] * N
    for i in range(N):
        A[i] = int(data[idx])
        idx += 1
        T[i] = int(data[idx])
        idx += 1
    
    # 差分更新用の配列
    diff = [0] * (N + 1)
    
    for _ in range(Q):
        L = int(data[idx]) - 1  # 0-indexed
        idx += 1
        R = int(data[idx]) - 1
        idx += 1
        X = int(data[idx])
        idx += 1
        
        diff[L] += X
        diff[R + 1] -= X
    
    # 累積和で各顧客の最終ポイント増分を計算
    final_add = list(accumulate(diff))[:N]
    
    count = 0
    for i in range(N):
        final_point = A[i] + final_add[i]
        if final_point >= T[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

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