概要

一列に並んだ山小屋について、隣接する山小屋間の標高差が \(K\) 以下なら連絡路があるとき、指定された2つの山小屋が同じエリア（連絡路で連続的につながった区間）に属するかを判定する問題です。累積和を用いて各クエリに \(O(1)\) で答えます。

考察

重要な気づき：「エリア」は連続区間である

問題文に「隣接する山小屋同士の連絡路で連結であるような極大な連続部分列」とあるように、エリアは山小屋の並びの中で連続した区間です。

つまり、山小屋 \(L\) と山小屋 \(R\)（\(L < R\)）が同じエリアに属する条件は：

\(L\) から \(R\) までの間のすべての隣接ペアに連絡路がある

ことと同値です。言い換えると、\(L\) と \(R\) の間に「途切れ（ブレーク）」が1つもなければ同じエリアです。

具体例

例えば \(N = 5\), \(K = 3\), \(A = [10, 12, 20, 18, 17]\) の場合：

隣接ペア	標高差	連絡路?
1-2	\(\|10-12\|=2\)	✅ (\(\leq 3\))
2-3	\(\|12-20\|=8\)	❌ (\(> 3\))
3-4	\(\|20-18\|=2\)	✅ (\(\leq 3\))
4-5	\(\|18-17\|=1\)	✅ (\(\leq 3\))

エリアは \(\{1, 2\}\) と \(\{3, 4, 5\}\) の2つです。山小屋1と山小屋2は同じエリア（Yes）、山小屋1と山小屋4は異なるエリア（No）です。

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

各クエリごとに \(L\) から \(R\) までの隣接ペアを1つずつ確認すると、1クエリあたり最大 \(O(N)\) かかり、全体で \(O(NQ)\) となって TLE の恐れがあります。

解決策：累積和

「途切れ」の有無を区間で高速に判定するには、累積和が使えます。途切れの個数の累積和を前計算しておけば、任意の区間の途切れの個数を \(O(1)\) で求められます。

アルゴリズム

1. 途切れの検出: 各 \(i\)（\(2 \leq i \leq N\)）について、\(|A_i - A_{i-1}| > K\) なら位置 \(i\) に「途切れ」があるとする。
2. 累積和の構築: \(\text{prefix}[i]\) を「位置 \(1\) から \(i\) までの途切れの個数」とする累積和配列を作る。
3. クエリ応答: 山小屋 \(L\) と \(R\) が同じエリアに属する条件は、\(L+1\) から \(R\) の間に途切れがないこと、すなわち： \(\text{prefix}[R] - \text{prefix}[L] = 0\) であれば Yes、そうでなければ No と出力する。

計算量

• 時間計算量: \(O(N + Q)\)（前処理に \(O(N)\)、各クエリに \(O(1)\)）
• 空間計算量: \(O(N)\)（累積和配列の分）

実装のポイント

• 1-indexed の扱い: 入力の山小屋番号は1始まりなので、累積和配列のインデックスと対応を間違えないように注意します。prefix[i] は「山小屋1から山小屋 \(i\) の間にある途切れの総数」と定義すると、区間 \([L, R]\) の途切れ数は prefix[R] - prefix[L] で求まります。
• 高速入出力: \(N, Q\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.readline での入力と、結果をリストにためてまとめて出力する工夫が重要です。

ソースコード

import sys
input = sys.stdin.readline

def main():
    N, K, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    # For each position i (0-indexed), check if mountain hut i and i+1 are connected
    # They are connected if |A[i] - A[i+1]| <= K
    # An "area" is a maximal contiguous subsequence of connected huts
    # We need to find for each hut, which area it belongs to
    # This is equivalent to: two huts L and R are in the same area iff
    # for all i in [L, R-1] (1-indexed), |A[i]-A[i+1]| <= K
    # i.e., there's no "break" between L and R
    
    # Precompute prefix array of "breaks"
    # breaks[i] = 1 if |A[i] - A[i-1]| > K (1-indexed, for i from 1 to N-1)
    # Then L and R are in same area iff sum of breaks from L+1 to R is 0
    # Using prefix sum we can answer in O(1)
    
    prefix = [0] * (N + 1)
    for i in range(1, N):
        prefix[i + 1] = prefix[i] + (1 if abs(A[i] - A[i - 1]) > K else 0)
    
    out = []
    for _ in range(Q):
        L, R = map(int, input().split())
        # Check if there's any break between position L and R (1-indexed)
        # Breaks are at positions 2, 3, ..., N (1-indexed)
        # Break at position i means hut i-1 and hut i are not connected
        # We need no breaks in [L+1, R]
        if prefix[R] - prefix[L] == 0:
            out.append("Yes")
        else:
            out.append("No")
    
    sys.stdout.write("\n".join(out) + "\n")

main()

---

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