概要

各木が収穫される回数を効率的に求め、果物の数と掛け合わせて収穫ポイントを計算する問題です。いもす法（差分配列）を使って区間への加算を高速に処理します。

考察

問題の本質

各木 \(i\) の収穫ポイントは「果物の数 \(A_i\)」×「収穫された回数」で計算できます。したがって、各木が何回収穫されたかを求めれば答えが出ます。

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

愚直に \(M\) 日分の収穫を処理すると、\(j\) 日目に木 \(L_j\) から \(R_j\) まで1つずつ収穫回数を加算することになります。

for j in range(M):
    for i in range(L[j], R[j]+1):
        count[i] += 1

この場合、最悪で各日に \(N\) 本すべての木を収穫する可能性があり、計算量は \(O(N \times M)\) となります。\(N, M\) が最大 \(2 \times 10^5\) のとき、\(4 \times 10^{10}\) 回の操作が必要となり、TLE（時間制限超過） になります。

解決策：いもす法

「区間 \([L, R]\) に一律 \(+1\) する」操作を効率化するために、いもす法（差分配列） を使います。

アルゴリズム

いもす法の仕組み

差分配列 diff を用意し、区間 \([L, R]\) に \(+1\) したいとき： - diff[L] += 1（ここから \(+1\) が始まる） - diff[R+1] -= 1（ここで \(+1\) が終わる）

最後に累積和を取ると、各位置の値が求まります。

具体例

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

差分配列への記録：

操作	diff[1]	diff[2]	diff[3]	diff[4]	diff[5]	diff[6]
初期	0	0	0	0	0	0
[2,4]に+1	0	+1	0	0	-1	0
[3,5]に+1	0	+1	+1	0	-1	-1

累積和を取る：

位置	1	2	3	4	5
収穫回数	0	1	2	2	1

木2は1回、木3と木4は2回、木5は1回収穫されることが分かります。

最終的な答え

各木 \(i\) について、収穫ポイント \(P_i = A_i \times \text{count}[i]\) を計算します。

計算量

• 時間計算量: \(O(N + M)\)
  • 差分配列への記録：各クエリ \(O(1)\) × \(M\) 回 = \(O(M)\)
  • 累積和の計算：\(O(N)\)
  • 最終結果の計算：\(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列と収穫回数配列にそれぞれ \(O(N)\) 必要

実装のポイント

1. 0-indexed と 1-indexed の変換: 問題文では木は1から番号が付いていますが、配列は0から始まるため、diff[L-1] += 1 と diff[R] -= 1 のように調整します。

2. 差分配列のサイズ: 配列外アクセスを防ぐため、diff は長さ \(N+1\) で確保します（\(R = N\) のとき diff[N] にアクセスするため）。

3. オーバーフロー対策: \(A_i\) が最大 \(10^9\)、収穫回数が最大 \(M = 2 \times 10^5\) なので、答えは最大 \(2 \times 10^{14}\) 程度になります。Pythonでは整数のオーバーフローを気にする必要はありませんが、他の言語では64ビット整数型を使う必要があります。

   ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 各木が何回収穫されたかをいもす法で計算
    # diff[i]: i番目の木から収穫回数が増加する量
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L, R = map(int, input().split())
        diff[L - 1] += 1  # 0-indexed に変換
        diff[R] -= 1
    
    # 累積和を取って各木の収穫回数を求める
    count = [0] * N
    current = 0
    for i in range(N):
        current += diff[i]
        count[i] = current
    
    # 各木のポイント = 果物の数 × 収穫回数
    result = [A[i] * count[i] for i in range(N)]
    
    print(' '.join(map(str, result)))

if __name__ == '__main__':
    main()

---

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