Overview

Consider two adjacent mountain huts as “connected” if their elevation difference is at most \(K\). The problem asks us to quickly determine, for each query \((L, R)\), whether the interval \([L, R]\) is continuously connected without any breaks.

Analysis

The key observation is that “belonging to the same area” is equivalent to all adjacent pairs \((i, i+1)\) between \(L\) and \(R\) having a connecting path (i.e., \(|A_i - A_{i+1}| \le K\)).

• If there is even one “break” where \(|A_i - A_{i+1}| > K\) along the way, the area is split there, so \(L\) and \(R\) cannot be in the same area.
• Conversely, if all adjacent pairs among \(L, L+1, \dots, R\) are connected, then by chaining connections we can always reach from one to the other, so they are in the same area.

Why a Naive Approach is Too Slow

If we check each query by iterating through \(i = L, \dots, R-1\) to see if there is a break, each query takes \(O(N)\) in the worst case, totaling \(O(NQ)\) overall. With \(N, Q \le 2 \times 10^5\), this is far too slow.

Solution

If we precompute the “breaks (bad edges)” and build a prefix sum, we can find the number of breaks in any interval in \(O(1)\).
If the number of breaks in the interval is 0, the answer is Yes; if there is even 1, the answer is No.

Algorithm

1. For each adjacent pair \((i, i+1)\) (\(i = 1..N-1\)):
   If \(|A_i - A_{i+1}| > K\), mark it as a “bad edge.”
2. Build a prefix sum pref of bad edges (explained in 0-index):
   
   • pref[t] = the number of bad edges among edges \((0,1), (1,2), \dots, (t-1,t)\)
     
   • That is, pref[i+1] = pref[i] + (abs(A[i]-A[i+1]) > K)
3. For query \((L, R)\) (1-indexed), the edges to check are
   \((L, L+1), (L+1, L+2), \dots, (R-1, R)\), a total of \(R - L\) edges.
   Converting to 0-index, the edge indices range from \(L-1\) to \(R-2\), so: $\( \text{bad} = \text{pref}[R-1] - \text{pref}[L-1] \)$
   • If bad == 0, there are no breaks along the way → Yes
   • Otherwise → No

Concrete Example

For example, with \(A = [10, 13, 30, 31]\), \(K = 5\): - \(|10-13| = 3\) (good) - \(|13-30| = 17\) (bad) - \(|30-31| = 1\) (good)

Query \((1, 2)\): 0 bad edges → Yes
Query \((1, 4)\): 1 bad edge along the way → No

Complexity

• Time complexity: Preprocessing \(O(N)\), each query \(O(1)\), so the total is \(O(N + Q)\)
• Space complexity: \(O(N)\) for the prefix sum array, etc.

Implementation Notes

• The “edges” contained in the query interval \([L, R]\) range from \((L, L+1)\) to \((R-1, R)\), so the prefix sum subtraction is pref[R-1] - pref[L-1]. Be careful here, as 1-index/0-index conversion mistakes are common.

• Since the input can be up to around \(4 \times 10^5\) lines, reading all at once with sys.stdin.buffer.read() is faster.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.