Overview

There are \(N\) mountain huts arranged in a line, and you can directly travel between adjacent huts if their elevation difference is at most \(K\). When we call the range reachable by repeatedly making such “direct travels” an “area,” the problem asks us to determine whether two given mountain huts \(L, R\) belong to the same area.

Analysis

1. Condition for Belonging to the Same Area

For mountain hut \(L\) and mountain hut \(R\) (\(L < R\)) to belong to the same area, all adjacent pairs of huts between them must be directly traversable. If the elevation difference between hut \(i\) and hut \(i+1\) (\(L \leq i < R\)) exceeds \(K\), the path is severed there, making it impossible to travel from \(L\) to \(R\).

In other words, the condition is: - “Between hut \(L\) and hut \(R\), there exists no adjacent pair whose elevation difference exceeds \(K\).”

2. Straightforward Approach and Its Limitations

For each query, if we loop from \(L\) to \(R-1\) checking whether any elevation difference exceeds \(K\), it takes up to \(O(N)\) time per query. Since there are \(Q\) queries, the total time complexity is \(O(NQ)\). Given the constraints of this problem where \(N, Q \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, which cannot finish within the time limit (typically around 2 seconds) and results in TLE.

3. Optimization Using Prefix Sums

The problem of “how many elements in a range satisfy a certain condition” can be efficiently solved using prefix sums. First, consider an array that represents whether the path between adjacent hut pair \((i, i+1)\) is “severed” using \(0\) or \(1\): - \(|A_i - A_{i+1}| > K\) → \(1\) (severed) - \(|A_i - A_{i+1}| \leq K\) → \(0\) (connected)

By precomputing the prefix sum array \(S\) of this array, we can determine the “total number of severed points” in any range \([L, R]\) in \(O(1)\). If the total is \(0\), the entire range is connected (belongs to the same area).

Algorithm

1. Prepare a prefix sum array \(S\) of length \(N\), and set \(S[0] = 0\).
2. For \(i = 1\) to \(N-1\), repeat the following:
   • If \(|A_i - A_{i+1}| > K\), then \(S[i] = S[i-1] + 1\)
   • Otherwise, \(S[i] = S[i-1]\)
   • This way, \(S[i]\) holds the total number of severed points among the first \(i+1\) huts from the left.
3. For each query \((L, R)\):
   • The number of severed points between hut \(L\) and hut \(R\) can be computed as \(S[R-1] - S[L-1]\).
   • If this value is \(0\), output Yes; otherwise, output No.

Complexity

• Time Complexity: \(O(N + Q)\)
  • Building the prefix sum takes \(O(N)\), and answering each query takes \(O(1)\), so the total is \(O(N + Q)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the elevation data \(A\) and the prefix sum array \(S\).

Implementation Notes

• Fast I/O: Since \(N\) and \(Q\) can be large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() instead of input().

• Index Management: The problem statement uses 1-indexed (1st, 2nd, …), but programs often use 0-indexed (0th, 1st, …), so be careful about the offset. In this code, by computing \(S[R-1] - S[L-1]\), we correctly check the adjacency relationships between hut \(L\) and hut \(R\).

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.