概要

\(N\) 個の地点に対して \(M\) 回の区間加算を行い、最終的に値が \(K\) 以上となる地点の個数を求める問題です。いもす法（差分配列） を用いることで効率的に解くことができます。

考察

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

最も単純な方法は、降雪のたびに地点 \(L_i\) から \(R_i\) までの各地点の積雪回数を1つずつ増やすことです。しかし、この方法では1回の降雪あたり最大 \(O(N)\) の操作が必要になり、全体で \(O(N \times M)\) となります。\(N\) が最大 \(10^6\)、\(M\) が最大 \(2 \times 10^5\) なので、最悪 \(2 \times 10^{11}\) 回の操作となり、制限時間内に終わりません（TLE）。

重要な気づき：区間加算はいもす法で高速化できる

「区間全体に同じ値を加算する」操作を何度も行う場面では、いもす法（差分配列） が非常に有効です。差分配列を使えば、1回の区間加算を \(O(1)\) で処理でき、最後にまとめて累積和を取ることで各地点の値を復元できます。

具体例

\(N = 5\)、降雪が \([2, 4]\) と \([3, 5]\) の2回あった場合を考えます。

差分配列への記録：

• \([2, 4]\)：diff[2] += 1, diff[5] -= 1
• \([3, 5]\)：diff[3] += 1, diff[6] -= 1

差分配列: [0, 0, 1, 1, 0, -1, -1]（インデックス0〜6）

累積和を取って復元：

地点	1	2	3	4	5
積雪回数	0	1	2	2	1

\(K = 2\) なら、地点3と地点4の2個が該当します。

アルゴリズム

1. サイズ \(N+2\) の差分配列 diff を0で初期化する。
2. 各降雪 \((L_i, R_i)\) に対して、diff[L_i] += 1、diff[R_i + 1] -= 1 とする。
3. 地点 \(1\) から \(N\) まで順に累積和を取りながら、現在の積雪回数が \(K\) 以上であればカウントを増やす。
4. カウントを出力する。

いもす法の仕組み： - diff[L] += 1 は「地点 \(L\) から積雪が始まる」ことを意味します。 - diff[R+1] -= 1 は「地点 \(R+1\) から積雪の効果が消える」ことを意味します。 - 累積和を取ると、各地点で「現在有効な降雪の回数」が正しく計算されます。

計算量

• 時間計算量: \(O(N + M)\)
  • 差分配列への記録に \(O(M)\)、累積和の計算とカウントに \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列のサイズ

実装のポイント

• 差分配列のサイズは N + 2 とする。diff[R_i + 1] で \(R_i = N\) のとき diff[N+1] にアクセスするため、インデックス \(N+1\) まで確保する必要がある。

• sys.stdin.buffer.read() でまとめて入力を読み込み、split() で分割することで、Pythonでも高速な入力処理が可能になる。1行ずつ input() を呼ぶと \(M\) が大きいときにTLEになる恐れがある。

• 累積和の計算とカウントを1つのループで同時に行うことで、余分な配列を作らずメモリと時間を節約している。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    diff = [0] * (N + 2)
    for i in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        diff[L] += 1
        diff[R + 1] -= 1
    
    count = 0
    current = 0
    for j in range(1, N + 1):
        current += diff[j]
        if current >= K:
            count += 1
    
    print(count)

main()

---

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