概要

\(N\) 個の山小屋が一列に並んでおり、隣り合う山小屋の標高差が \(K\) 以下であれば直接行き来が可能です。この「直接の行き来」を繰り返して移動できる範囲を一つの「エリア」と呼ぶとき、与えられた2つの山小屋 \(L, R\) が同じエリアに属するかを判定する問題です。

考察

1. 同じエリアに属するための条件

山小屋 \(L\) と山小屋 \(R\) (\(L < R\)) が同じエリアに属するためには、その間にあるすべての隣り合う山小屋同士が直接行き来できる必要があります。 もし、山小屋 \(i\) と \(i+1\) (\(L \leq i < R\)) の標高差が \(K\) を超えていた場合、そこで連絡路が途切れてしまうため、 \(L\) から \(R\) へ行くことはできません。

つまり、判定条件は以下のようになります。 - 「\(L\) 番目から \(R\) 番目までの間に、標高差が \(K\) を超える隣接ペアが一つも存在しない」

2. 素直な方法とその限界

各クエリに対して、 \(L\) から \(R-1\) までループを回して「標高差が \(K\) を超える箇所があるか」をチェックすると、1つのクエリにつき最大 \(O(N)\) の時間がかかります。 クエリの数は \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となります。 本問題の制約では \(N, Q \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2秒程度）に間に合いません（TLE）。

3. 累積和による高速化

「範囲内に条件を満たすものがいくつあるか」という問題は、累積和を用いることで高速化できます。 まず、隣り合う山小屋のペア \((i, i+1)\) について、連絡路が「切断」されているかどうかを \(0\) か \(1\) で表す配列を考えます。 - \(|A_i - A_{i+1}| > K\) ならば \(1\)（切断） - \(|A_i - A_{i+1}| \leq K\) ならば \(0\)（連結）

この配列の累積和 \(S\) を事前に計算しておけば、任意の範囲 \([L, R]\) における「切断箇所の合計数」を \(O(1)\) で求めることができます。 合計数が \(0\) であれば、その範囲はすべて繋がっている（同じエリアである）と判定できます。

アルゴリズム

1. 長さ \(N\) の累積和配列 \(S\) を用意し、 \(S[0] = 0\) とします。
2. \(i = 1\) から \(N-1\) まで以下を繰り返します。
   • \(|A_i - A_{i+1}| > K\) ならば \(S[i] = S[i-1] + 1\)
   • そうでなければ \(S[i] = S[i-1]\)
   • ※これにより、 \(S[i]\) は「左から \(i+1\) 番目までの山小屋の間にある切断箇所の総数」を保持します。
3. 各クエリ \((L, R)\) に対して：
   • \(L\) 番目から \(R\) 番目の間の切断数は \(S[R-1] - S[L-1]\) で計算できます。
   • この値が \(0\) なら Yes、そうでなければ No を出力します。

計算量

• 時間計算量: \(O(N + Q)\)
  • 累積和の構築に \(O(N)\)、各クエリの回答に \(O(1)\) かかるため、全体で \(O(N + Q)\) です。
• 空間計算量: \(O(N)\)
  • 標高データ \(A\) と累積和配列 \(S\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(Q\) が大きいため、Pythonでは input() ではなく sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。
• インデックスの管理: 問題文は 1-indexed（1番目、2番目…）ですが、プログラム内では 0-indexed（0番目、1番目…）として扱うことが多いため、ズレに注意が必要です。今回のコードでは \(S[R-1] - S[L-1]\) とすることで、 \(L\) 番目から \(R\) 番目までの間の隣接関係を正しく判定しています。

ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # 大量の入力を高速に処理するために sys.stdin.read().split() を使用
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 山小屋の数, K: 標高差の閾値, Q: 質問の数
    N = int(input_data[0])
    K = int(input_data[1])
    Q = int(input_data[2])
    
    # 各山小屋の標高 A (0-indexed)
    A = list(map(int, input_data[3:3+N]))
    
    # 累積和配列 S を作成
    # S[i] は、最初の i 個の隣接ペアのうち、標高差が K を超える（連絡路がない）ものの数
    # 山小屋 i と i+1 の間の連絡路の状態を S[i+1] に反映させる
    S = [0] * N
    for i in range(N - 1):
        # 隣り合う山小屋の標高差が K より大きい場合、連絡路は「切断」されている
        if abs(A[i] - A[i+1]) > K:
            S[i+1] = S[i] + 1
        else:
            S[i+1] = S[i]
            
    # 各質問 (L, R) に対して判定を行う
    results = []
    query_start = 3 + N
    for i in range(Q):
        # L, R は 1-indexed で与えられる
        L = int(input_data[query_start + 2*i])
        R = int(input_data[query_start + 2*i + 1])
        
        # 山小屋 L と R が同じエリアに属するためには、
        # L から R までのすべての隣接ペアに連絡路が存在する必要がある。
        # これは、L-1 番目から R-2 番目までのペアの間に「切断」がないことと同義。
        # 累積和を用いると、その範囲の切断数は S[R-1] - S[L-1] で求められる。
        if S[R-1] - S[L-1] == 0:
            results.append("Yes")
        else:
            results.append("No")
            
    # すべての結果を改行で結合して一括出力
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

---

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