概要

隣り合う山小屋間の標高差が \(K\) 以下なら「つながる」と考え、質問 \((L, R)\) について区間 \([L, R]\) が途中で途切れずにつながっているかを高速に判定する問題です。

考察

重要な観察は、「同じエリアに属する」ことは \(L\) から \(R\) までの間にある隣接ペア \((i, i+1)\) がすべて連絡路あり（つまり \(|A_i-A_{i+1}| \le K\)）であることと同値だという点です。

• もし途中に一箇所でも \(|A_i-A_{i+1}| > K\) となる“切れ目”があると、そこでエリアが分断されるため \(L\) と \(R\) は同じエリアになれません。
• 逆に、\(L, L+1, \dots, R\) の間のすべての隣接がつながっていれば、連鎖して必ず到達できるので同じエリアです。

素朴な方法が遅い理由

各質問ごとに \(i=L,\dots,R-1\) を順に見て「切れ目があるか」を調べると、1 クエリあたり最悪 \(O(N)\)、合計で最悪 \(O(NQ)\) となり、\(N,Q \le 2\times 10^5\) では到底間に合いません。

解決策

「切れ目（悪い辺）」の個数を前計算して累積和にしておけば、区間内の切れ目の数を \(O(1)\) で求められます。
区間内の切れ目が 0 個なら Yes、1 個でもあれば No です。

アルゴリズム

1. 各隣接ペア \((i, i+1)\)（\(i=1..N-1\)）について
   \(|A_i - A_{i+1}| > K\) なら「悪い辺」とする。
2. 悪い辺の累積和 pref を作る（0-index で説明）
   
   • pref[t] = 辺 \((0,1),(1,2),\dots,(t-1,t)\) の中にある悪い辺の数
     
   • つまり pref[i+1] = pref[i] + (abs(A[i]-A[i+1]) > K)
3. クエリ \((L, R)\)（1-index）について、調べるべき辺は
   \((L,L+1),(L+1,L+2),\dots,(R-1,R)\) の合計 \(R-L\) 本。
   これは 0-index にすると辺のインデックスが \(L-1\) から \(R-2\) までなので、 \( \text{bad} = \text{pref}[R-1] - \text{pref}[L-1] \)
   • bad == 0 なら途中に切れ目なし → Yes
   • それ以外 → No

具体例

例えば \(A=[10, 13, 30, 31]\), \(K=5\) のとき

• \(|10-13|=3\)（良い）
• \(|13-30|=17\)（悪い）
• \(|30-31|=1\)（良い）

クエリ \((1,2)\) は悪い辺が 0 → Yes
クエリ \((1,4)\) は途中に悪い辺が 1 → No

計算量

• 時間計算量: 前計算 \(O(N)\)、各クエリ \(O(1)\) なので合計 \(O(N+Q)\)
• 空間計算量: 累積和配列などで \(O(N)\)

実装のポイント

• クエリの区間 \([L, R]\) に含まれる「辺」は \((L, L+1)\) から \((R-1, R)\) までであり、累積和の引き算は pref[R-1] - pref[L-1] になる点に注意します（1-index/0-index の対応ミスが起きやすい）。
• 入力が最大 \(4\times 10^5\) 行規模になり得るため、sys.stdin.buffer.read() でまとめて読み込むと高速です。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    K = next(it)
    Q = next(it)

    A = [next(it) for _ in range(N)]

    pref = [0] * N  # pref[t] = number of "bad" edges among edges 0..t-1 (t edges)
    for i in range(N - 1):
        pref[i + 1] = pref[i] + (1 if abs(A[i] - A[i + 1]) > K else 0)

    out = []
    for _ in range(Q):
        L = next(it)
        R = next(it)
        bad = pref[R - 1] - pref[L - 1]
        out.append("Yes" if bad == 0 else "No")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。