概要

\(N\) 本の木に対して \(M\) 回の範囲更新（収穫）を行い、最終的な各木の累計ポイントを求める問題です。各木のポイントは「（その木にある果物の数）\(\times\)（その木で収穫が行われた回数）」で計算できます。

考察

素朴な方法とその限界

各日の収穫作業ごとに、指定された範囲 \(L_j\) から \(R_j\) までの木を一つずつ確認してポイントを加算していく方法が考えられます。 しかし、この方法では最悪の場合、毎日すべての木（\(N\) 本）を処理することになり、計算量は \(O(N \times M)\) となります。本問題の制約では \(N, M \le 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

効率的なアプローチ

各木 \(i\) について、最終的な収穫ポイント \(P_i\) は以下の式で表せます。 $\(P_i = A_i \times (\text{木 } i \text{ が収穫された回数})\)$

\(A_i\) は最初から決まっているため、「各木が合計で何回収穫されたか」を効率よく数え上げることができれば、この問題は解けます。 特定の範囲に一括で値を加算する操作を高速に行う手法として、「いもす法（差分配列）」が非常に有効です。

アルゴリズム

いもす法を用いた手順

1. 差分配列の準備: 長さ \(N+2\) の配列 diff を \(0\) で初期化します。
2. 範囲更新の記録: 各収穫範囲 \([L_j, R_j]\) に対して、以下の操作を行います。
   • diff[L_j] に \(1\) を加える
   • diff[R_j + 1] から \(1\) を引く
3. 累積和の計算: diff 配列の累積和をとることで、各木 \(i\) が収穫された回数 \(C_i\) を求めます。
   • \(C_i = \sum_{k=1}^{i} \text{diff}[k]\)
4. 最終結果の計算: 各木について \(A_i \times C_i\) を計算して出力します。

この手法を用いると、各クエリ（収穫作業）を \(O(1)\) で処理でき、最後の累積和計算も \(O(N)\) で終わるため、大幅に高速化できます。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込み、差分配列への記録（\(M\) 回）、累積和の計算（\(N\) 回）、結果の出力（\(N\) 回）のすべてが線形時間で処理されます。
• 空間計算量: \(O(N)\)
  • 果物の数 \(A_i\)、差分配列、収穫回数を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, M\) が大きいため、Pythonでは sys.stdin.read().split() や sys.stdout.write() を使用して入出力を高速化するのが一般的です。

• インデックスの管理: 問題文は 1-indexed（木 1 〜 \(N\)）ですが、プログラム内での配列の扱いや差分配列のサイズ（\(R+1\) へのアクセス）に注意が必要です。

• 大きな数値: \(A_i \le 10^9\) かつ \(M \le 2 \times 10^5\) であるため、最終的なポイントは最大で \(2 \times 10^{14}\) 程度になります。Pythonは標準で多倍長整数をサポートしているため、オーバーフローの心配はありません。

  ソースコード

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # A_i の読み込み (0-indexedにするため、前にダミーを入れるかそのまま扱う)
    A = list(map(int, input_data[2:2+N]))
    
    # いもす法（差分配列）を用いて、各木が何回収穫されたかをカウントする
    # 1-indexedの範囲 [L, R] に対応するため、サイズ N+2 の配列を用意
    diff = [0] * (N + 2)
    
    ptr = 2 + N
    for _ in range(M):
        L = int(input_data[ptr])
        R = int(input_data[ptr+1])
        diff[L] += 1
        diff[R + 1] -= 1
        ptr += 2
        
    # 累積和をとり、各木の収穫回数 C_i を求める
    counts = [0] * (N + 1)
    current_count = 0
    for i in range(1, N + 1):
        current_count += diff[i]
        counts[i] = current_count
        
    # 各木の収穫ポイント P_i = A_i * C_i を計算
    results = []
    for i in range(N):
        # Aは0-indexedなので A[i]、countsは1-indexedなので counts[i+1]
        results.append(str(A[i] * counts[i+1]))
        
    # 結果をまとめて出力
    sys.stdout.write(" ".join(results) + "\n")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。