概要

各区間に対して、その区間に含まれる木の収穫回数をカウントし、各木の果物の数と収穫回数の積として累計収穫ポイントを求めます。

考察

この問題では、\(M\) 日分の収穫情報（それぞれが区間 \([L_j, R_j]\)）が与えられ、各区間内のすべての木に対して「収穫回数が1増える」という処理が必要です。そして最終的に、各木 \(i\) の収穫ポイントは「\(A_i \times (\text{収穫回数})\)」となります。

素朴な方法では？

一番素直な方法としては、各日ごとに区間 \([L_j, R_j]\) のすべての木のカウンタをインクリメントすることです。しかし、区間の長さが最大 \(N\)、日数も最大 \(2 \times 10^5\) あるため、全体で最大 \(2 \times 10^{10}\) 回程度の操作が必要になり、時間制限（たいてい 1 秒程度）内に収まりません（TLE）。

効率的な方法は？

そこで登場するのが「imos法（いもす法）」です。これは区間に対する加算処理を効率的に行うためのテクニックで、差分更新＋累積和を利用します。

imos法のアイデア：

• 各区間 \([L, R]\) への加算を、差分配列 diff に対して
  • diff[L] += 1
  • diff[R+1] -= 1 とすることで、区間全体に一様に加算するのではなく、差分だけ記録します。
• 最後に累積和を取ることで、各要素に実際に加算された値が得られます。

この方法なら、各クエリは定数時間で処理でき、最後に一度だけ累積和を計算すればよいので、全体で \(O(N + M)\) で解けます。

アルゴリズム

1. 入力を高速に読み込みます（sys.stdin.read を使用）。
2. 各日 \(j\) の収穫区間 \([L_j, R_j]\) に対応する差分配列 diff を更新します（imos法）。
3. diff の累積和を計算して、各木の収穫回数 count[i] を求めます。
4. 各木の収穫ポイントは \(A_i \times \text{count}[i]\) で求められます。
5. 結果を出力します。

計算量

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

実装のポイント

• 入力のインデックスは1-indexedなので、内部処理では0-indexedに変換する必要があります。
• 差分配列 diff はサイズを \(N+1\) にしておき、範囲外アクセスを防ぎます。
• 高速入力（sys.stdin.read）を使用しないとPythonではTLEすることがあります。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    # 差分更新用の配列
    diff = [0] * (N + 1)
    
    idx = 2 + N
    for _ in range(M):
        L = int(data[idx]) - 1   # 0-indexed
        R = int(data[idx+1]) - 1
        idx += 2
        diff[L] += 1
        diff[R+1] -= 1
    
    # 差分を累積和して、各木の収穫回数を求める
    count = [0] * N
    c = 0
    for i in range(N):
        c += diff[i]
        count[i] = c
    
    # 収穫ポイント = 果物の数 × 収穫回数
    points = [A[i] * count[i] for i in range(N)]
    
    print(' '.join(map(str, points)))

if __name__ == "__main__":
    main()

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