概要

\(N\) 台のスマートフォンに対して \(Q\) 回の範囲減少クエリが与えられるので、すべてのクエリ処理後の各スマートフォンのバッテリー残量を求める問題です。

考察

重要な気づき

この問題では、バッテリー残量は \(0\) 以下にならないという制約があります。しかし、よく考えると、各スマートフォンに対して「何回通知が来たか」さえ分かれば、最終的なバッテリー残量は以下の式で計算できます：

\[\text{最終残量} = \max(0, \text{初期残量} - \text{通知回数})\]

これは、通知が来るたびに \(1\) 減少し、\(0\) 以下にはならないという条件を満たします。

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

素朴に各クエリで区間 \([L, R]\) のすべての要素を \(1\) ずつ減らすと、1回のクエリで最大 \(O(N)\) の計算が必要です。\(Q\) 回のクエリがあるので、全体で \(O(NQ)\) となり、\(N, Q\) が最大 \(2 \times 10^5\) の場合、最大 \(4 \times 10^{10}\) 回の操作が必要となりTLEします。

解決策：imos法

区間への加算クエリを効率的に処理するために imos法（いもす法） を使います。imos法を使えば、すべてのクエリを \(O(Q)\) で処理し、その後 \(O(N)\) で各位置への影響を計算できます。

アルゴリズム

imos法の仕組み

imos法は、区間 \([L, R]\) への加算を以下の2つの操作に置き換えます：

1. 位置 \(L\) に \(+1\) を記録
2. 位置 \(R+1\) に \(-1\) を記録

すべてのクエリを処理した後、配列の累積和を取ると、各位置への加算回数が求まります。

具体例

\(N = 5\) で、クエリ \([2, 4]\) と \([3, 5]\) がある場合：

初期配列:  [0, 0, 0, 0, 0, 0]  (index 1〜5を使用)
          
クエリ[2,4]: index 2 に +1, index 5 に -1
配列:      [0, +1, 0, 0, -1, 0]

クエリ[3,5]: index 3 に +1, index 6 に -1
配列:      [0, +1, +1, 0, -1, -1]

累積和:    [0, 1, 2, 2, 1, 0]

累積和の結果、位置 \(2\) には \(1\) 回、位置 \(3, 4\) には \(2\) 回、位置 \(5\) には \(1\) 回の通知が来ることが分かります。

処理の流れ

1. 差分配列 imos を用意し、各クエリ \((L, R)\) に対して imos[L] += 1, imos[R+1] -= 1 を実行
2. 累積和を取って各位置への通知回数 notifications[i] を計算
3. 各スマートフォン \(i\) の最終残量を \(\max(0, S_i - \text{notifications}[i])\) で計算

計算量

• 時間計算量: \(O(N + Q)\)
  • クエリの処理: \(O(Q)\)
  • 累積和の計算: \(O(N)\)
  • 最終結果の計算: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列と通知回数配列に \(O(N)\) のメモリを使用

実装のポイント

• 1-indexed と 0-indexed の変換に注意。問題文は 1-indexed、Python配列は 0-indexed なので、適切に対応させる

• imos 配列は index \(R+1\) にアクセスするため、サイズを \(N+2\) 以上確保する

• max(0, ...) を忘れると、バッテリー残量が負になってしまうので注意

  ソースコード

import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = list(map(int, input().split()))
    
    # イベントを各位置ごとに管理
    # start[i]: 位置iから始まるイベントのリスト（終了位置を格納）
    # imos法で各位置に何回通知が来るかを計算
    imos = [0] * (N + 2)
    
    for _ in range(Q):
        L, R = map(int, input().split())
        imos[L] += 1
        imos[R + 1] -= 1
    
    # 累積和を取って各位置への通知回数を計算
    notifications = [0] * (N + 1)
    current = 0
    for i in range(1, N + 1):
        current += imos[i]
        notifications[i] = current
    
    # 各スマートフォンの最終バッテリー残量を計算
    result = []
    for i in range(N):
        # i番目のスマートフォン（1-indexed では i+1）
        final_battery = max(0, S[i] - notifications[i + 1])
        result.append(final_battery)
    
    print(' '.join(map(str, result)))

if __name__ == '__main__':
    main()

---

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