概要

一直線上に並ぶ地点の中にある桜の木から落ちる花びらの総数を求めます。高橋君は地点 \(S\) から \(T\) へ最短距離で移動し、通った地点にある桜の木から花びらを受け取ります。

考察

この問題では、高橋君が地点 \(S\) から \(T\) までの区間内にあるすべての桜の木について、それぞれに対応する花びらの枚数を合計する必要があります。

素朴な方法とその問題点

単純には、地点 \(S\) から \(T\) までのすべての地点を走査して、そこに桜の木があるかどうかを毎回確認すればよいように思えます。しかし、地点の数 \(N\) は最大で \(10^9\) にも達するため、この方法では現実的な時間内に処理できません（TLE）。

さらに、入力で与えられるのは桜の木のある「地点」だけなので、すべての地点を事前に配列などで持つことも不可能です。

改善策：区間の扱いと累積和

そこで重要な観察があります： - 移動は一直線であり、「通る区間」は単なる区間 \([ \min(S,T), \max(S,T) ]\) と考えて良い。 - 各桜の木の位置が分かっていれば、この区間に含まれる木だけを考慮すればよい。

したがって、以下のような手順を考えます： 1. 桜の木の位置情報をソートしておく。 2. 区間 \([\min(S,T), \max(S,T)]\) 内にある木の位置を効率的に求めたい → 二分探索が有効。 3. その区間内の木の花びらの合計値を高速に求めたい → 累積和を使うことで部分和を定数時間で取得可能。

これにより、非常に大きな \(N\) に対しても効率的に答えを求めることができます。

アルゴリズム

1. 入力を読み込み、桜の木の情報を \((P_i, V_i)\) のペアとしてリストに保存。
2. 桜の木の位置 \(P_i\) でリストを昇順にソートする。
3. ソートされた花びら数 \(V_i\) に対して、累積和を前もって計算しておく。
4. 高橋君の移動区間 \([start, end]\) を \(\min(S, T)\) と \(\max(S, T)\) とする。
5. 二分探索（bisect_leftなど）により、区間 \([start, end]\) 内に含まれる木の開始・終了インデックスを求める。
6. 累積和テーブルを使い、該当区間の花びらの合計を高速に計算して出力する。

計算量

• 時間計算量: \(O(M \log M)\) （主にソートによる）
• 空間計算量: \(O(M)\)

※ \(M\) は桜の木の本数で最大 \(2 \times 10^5\)

実装のポイント

• 入力が非常に多いので、高速な入力処理（例：sys.stdin.read()）を行うこと。

• bisect_left(a, x) はソート済みリスト a 上で要素 x を挿入すべき場所を返す（境界条件に注意）。

• 区間 \([L, R]\) の和を得たいとき、累積和 cumsum を用いると cumsum[R+1] - cumsum[L] で求められる（cumsum[0] = 0 としておく）。

  ソースコード

import sys
from bisect import bisect_left

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    S = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    # 桜の木の位置を基準にソートするため、(位置, 花びら数) のリストを作成
    trees = []
    for _ in range(M):
        p = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        trees.append((p, v))
    
    # 位置でソート
    trees.sort()
    positions = [t[0] for t in trees]
    petals = [t[1] for t in trees]
    
    # 累積和を計算（前処理）
    cumsum = [0]
    for v in petals:
        cumsum.append(cumsum[-1] + v)
    
    # 開始点と終了点を範囲として統一（開始 < 終了にする）
    start, end = min(S, T), max(S, T)
    
    # 二分探索で範囲内の木のインデックスを取得
    left_idx = bisect_left(positions, start)
    right_idx = bisect_left(positions, end + 1)
    
    # 累積和を使って範囲内の合計を高速に計算
    total = cumsum[right_idx] - cumsum[left_idx]
    print(total)

if __name__ == "__main__":
    main()

---

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