概要

各日の区間収穫によって「各木が何回収穫されたか」を数え、最後にその回数に果物数 \(A_i\) を掛けて累計ポイントを求めます。

考察

1回収穫されるたびに、木 \(i\) には常に \(A_i\) ポイントが加算されます（果物は減らないため）。
したがって最終的なポイントは

• 木 \(i\) が収穫された回数を \(C_i\) とすると
• \(P_i = A_i \times C_i\)

となります。

ここで素朴に、各日 \([L_j, R_j]\) の全ての木について回数を \(+1\) すると、最悪で区間長が \(N\) の操作を \(M\) 回行うことになり、時間計算量は \(O(NM)\)（最大で \(4 \times 10^{10}\) 程度）となって確実に TLE します。

そこで、「区間に一括で +1 する操作」を高速に処理する必要があります。典型的には 差分配列（いもす法） を使うと、各区間更新を \(O(1)\) で記録でき、最後に累積和を取って \(C_i\) を求められます。

例えば \(N=5\) で区間が \([2,4]\) のとき、差分配列 diff に - diff[2] += 1 - diff[5] -= 1（= diff[R+1] -= 1） と入れておくと、diff の累積和を取ったときに index 2〜4 のみが +1 された回数になります。

アルゴリズム

1. 長さ \(N+2\) の差分配列 diff を 0 で初期化する。
2. 各日 \(j\) の区間 \([L_j, R_j]\) に対して
   • diff[L_j] += 1
   • diff[R_j + 1] -= 1 と記録する。
3. \(i=1\) から \(N\) まで順に cur += diff[i] と累積和を取り、これを \(C_i\)（木 \(i\) の収穫回数）とする。
4. 各木について \(P_i = A_i \times C_i\) を計算して出力する。

計算量

• 時間計算量: \(O(N+M)\)（区間の記録が \(O(M)\)、累積和と出力が \(O(N)\)）
• 空間計算量: \(O(N)\)（差分配列と出力用）

実装のポイント

• diff[R+1] を扱うために、配列サイズを N+2 にして範囲外アクセスを防ぎます。

• 入力が最大 \(4 \times 10^5\) 個以上になるため、sys.stdin.buffer.read() でまとめて読み取ると高速です。

• 値は最大で \(A_i \le 10^9\)、\(C_i \le M \le 2 \times 10^5\) なので、積は最大 \(2 \times 10^{14}\) 程度になります。Python の int なら安全に扱えます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    A = [next(it) for _ in range(N)]

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

    res = []
    cur = 0
    for i in range(1, N + 1):
        cur += diff[i]
        res.append(str(A[i - 1] * cur))

    sys.stdout.write(" ".join(res))

if __name__ == "__main__":
    main()

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