Overview

Given a row of mountain huts, where adjacent huts have a connecting path if their elevation difference is at most \(K\), we determine whether two specified mountain huts belong to the same area (a contiguous segment connected by paths). We use prefix sums to answer each query in \(O(1)\).

Analysis

Key Insight: “Areas” Are Contiguous Segments

As stated in the problem, an area is a “maximal contiguous subsequence that is connected by paths between adjacent mountain huts.” In other words, an area is a contiguous segment within the arrangement of mountain huts.

Therefore, the condition for mountain hut \(L\) and mountain hut \(R\) (\(L < R\)) to belong to the same area is:

All adjacent pairs between \(L\) and \(R\) have connecting paths.

In other words, if there are no “breaks” between \(L\) and \(R\), they belong to the same area.

Concrete Example

For example, with \(N = 5\), \(K = 3\), \(A = [10, 12, 20, 18, 17]\):

Adjacent Pair	Elevation Difference	Path?
1-2	$	10-12
2-3	$	12-20
3-4	$	20-18
4-5	$	18-17

There are two areas: \(\{1, 2\}\) and \(\{3, 4, 5\}\). Mountain huts 1 and 2 are in the same area (Yes), while mountain huts 1 and 4 are in different areas (No).

Problem with the Naive Approach

If we check each adjacent pair from \(L\) to \(R\) for every query, each query takes up to \(O(N)\), resulting in \(O(NQ)\) overall, which risks TLE.

Solution: Prefix Sums

To efficiently determine whether there are any breaks in a given range, we can use prefix sums. By precomputing a prefix sum of the number of breaks, we can find the number of breaks in any range in \(O(1)\).

Algorithm

1. Detect breaks: For each \(i\) (\(2 \leq i \leq N\)), if \(|A_i - A_{i-1}| > K\), there is a “break” at position \(i\).
2. Build prefix sums: Construct a prefix sum array where \(\text{prefix}[i]\) is “the number of breaks from position \(1\) to position \(i\).”
3. Answer queries: Mountain huts \(L\) and \(R\) belong to the same area if and only if there are no breaks between positions \(L+1\) and \(R\), i.e.: $\(\text{prefix}[R] - \text{prefix}[L] = 0\)$ If so, output Yes; otherwise, output No.

Complexity

• Time complexity: \(O(N + Q)\) (\(O(N)\) for preprocessing, \(O(1)\) per query)
• Space complexity: \(O(N)\) (for the prefix sum array)

Implementation Notes

• 1-indexed handling: Since the mountain hut numbers in the input are 1-based, be careful to correctly map them to the prefix sum array indices. If we define prefix[i] as “the total number of breaks between mountain hut 1 and mountain hut \(i\),” then the number of breaks in the range \([L, R]\) is prefix[R] - prefix[L].

• Fast I/O: Since \(N, Q\) can be as large as \(2 \times 10^5\), in Python it is important to use sys.stdin.readline for input and to collect results in a list for batch output.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.