概要

山小屋が一直線上に並んでおり、隣接する山小屋の標高差が \(K\) 以下であれば連絡路が存在します。複数の質問に対し、指定された2つの山小屋が同じ連結成分（エリア）に属するかを判定する問題です。

考察

この問題では、まず「同じエリアに属する」とはどういうことかを考えます。これは、2つの山小屋の間に連鎖的に連絡路が存在することを意味します。つまり、その間にあるすべての隣接する山小屋ペアが連絡路で結ばれていれば、同じエリアに属します。

例えば、山小屋1と山小屋4が同じエリアに属するためには、

• 山小屋1と2の間に連絡路があり、
  
• 山小屋2と3の間に連絡路があり、
  
• 山小屋3と4の間に連絡路がある
  

必要があります。つまり、区間 \([L, R]\) 内のすべての隣接ペアが連絡路を持っているかどうかを確認すればよいです。

素朴な方法として、毎回区間内の隣接ペアを一つずつ確認する方法がありますが、これだと最悪の場合 \(O(NQ)\) の計算量となり、制約が大きいため時間内に終わらない可能性があります（TLE）。

そこで、「区間内の連絡路の数」を高速に求めることができるように前処理を行います。具体的には、隣接する山小屋の間に連絡路があるかどうかを配列で管理し、その累積和（接頭和）を事前に計算しておくことで、任意の区間での連絡路の数を \(O(1)\) で求めることができます。

アルゴリズム

1. 各隣接する山小屋のペアについて、標高差が \(K\) 以下かどうかを判定し、連絡路があれば 1、そうでなければ 0 を記録した配列 connected を作ります。
2. connected の累積和を計算し、prefix_sum 配列を作ります。これにより、任意の区間 \([L, R]\) 内にある連絡路の数を \(O(1)\) で求められます。
3. 各クエリに対して：
   • 区間 \([L, R]\) に含まれる隣接ペアの数は \(R - L\) 個です。
   • この区間内の連絡路の数が \(R - L\) に等しければ、すべての隣接ペアが連絡路を持つので Yes を出力します。そうでなければ No を出力します。

具体例

入力例：

5 3 2
1 4 6 9 7
1 3
2 5

• 山小屋の標高：\([1, 4, 6, 9, 7]\)
• 隣接差の絶対値：\([3, 2, 3, 2]\)
• すべてが \(K=3\) 以下なので、すべての隣接ペアに連絡路があります。
• connected = [1, 1, 1, 1]
• 累積和：prefix_sum = [0, 1, 2, 3, 4]

クエリ1：山小屋1と3 → 間のペア数 = 2、連絡路数 = prefix_sum[2] - prefix_sum[0] = 2 → Yes
クエリ2：山小屋2と5 → 間のペア数 = 3、連絡路数 = prefix_sum[4] - prefix_sum[1] = 3 → Yes

計算量

• 時間計算量: \(O(N + Q)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 1-indexed で入力が与えられるので、内部処理では 0-indexed に変換する必要があります。
• 累積和の最初に 0 を追加しておくと、区間和の計算が簡単になります。
• 大量の入力を高速に読み込むために sys.stdin.read を使用しています。

ソースコード

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    Q = int(data[2])
    
    A = list(map(int, data[3:3+N]))
    
    # 隣接する山小屋間に連絡路があるかをチェック
    connected = [0] * (N - 1)
    for i in range(N - 1):
        if abs(A[i] - A[i+1]) <= K:
            connected[i] = 1
    
    # 接頭和を計算して、任意の区間での連絡路の数をO(1)で取得できるようにする
    prefix_sum = [0] + list(accumulate(connected))
    
    # 各質問に対して処理
    results = []
    index = 3 + N
    for _ in range(Q):
        L = int(data[index]) - 1  # 0-indexedにする
        R = int(data[index+1]) - 1
        index += 2
        
        # 区間[L, R)に含まれる連絡路の数
        links = prefix_sum[R] - prefix_sum[L]
        
        # [L, R]の間の隣接ペアの数
        total_pairs = R - L
        
        # すべての隣接ペアが連絡路を持つ場合、同じエリアに属する
        if links == total_pairs:
            results.append("Yes")
        else:
            results.append("No")
    
    print("\n".join(results))

if __name__ == "__main__":
    main()

---

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