Overview

Given that there is a trail between adjacent mountain huts if their elevation difference is at most \(K\), the problem asks us to determine, for multiple queries, whether two specified mountain huts belong to the same area.

Analysis

A naive approach of checking connectivity via BFS or DFS for each query would take \(O(NQ)\) time in the worst case, which is far too slow given the constraints \(N, Q \leq 2 \times 10^5\). Instead, we realize that we can identify all areas in advance and then, for each query, simply check whether the two huts belong to the same area.

A key observation is that since trails only exist between adjacent mountain huts, areas form contiguous intervals. However, it is important to note that areas are not necessarily single contiguous intervals (for example, an area is split at positions where the elevation difference exceeds \(K\)).

Algorithm

We use a Union-Find (Disjoint Set Union, DSU) data structure. For every pair of adjacent mountain huts \((i, i+1)\), if the absolute difference in their elevations is at most \(K\), we merge them using the union operation. This ensures that mountain huts belonging to the same area end up in the same tree (connected component).

For each query, we use the find operation to check whether \(L_j\) and \(R_j\) belong to the same tree. If they do, we output Yes; otherwise, we output No.

Complexity

• Time complexity: \(O(N \alpha(N) + Q \alpha(N))\)
  • Union-Find operations involve the inverse Ackermann function \(\alpha(N)\), which can be treated as a constant, so the overall time is nearly linear.
• Space complexity: \(O(N)\)
  • For the parent array and rank array.

Implementation Notes

• Efficiency is achieved by implementing Union-Find with path compression and union by rank.

• Since the mountain hut numbers in the input are 1-indexed, convert them to 0-indexed.

• It is sufficient to check only pairs of adjacent mountain huts (due to the contiguity of areas).

• To handle large inputs, read all input at once using sys.stdin.read().

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); K = int(next(it)); Q = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    queries = []
    for i in range(Q):
        L = int(next(it)) - 1
        R = int(next(it)) - 1
        queries.append((L, R))
    
    parent = list(range(N))
    rank = [0] * N
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        rx = find(x)
        ry = find(y)
        if rx == ry:
            return
        if rank[rx] < rank[ry]:
            parent[rx] = ry
        elif rank[rx] > rank[ry]:
            parent[ry] = rx
        else:
            parent[ry] = rx
            rank[rx] += 1
    
    for i in range(N-1):
        if abs(A[i] - A[i+1]) <= K:
            union(i, i+1)
    
    res = []
    for L, R in queries:
        if find(L) == find(R):
            res.append("Yes")
        else:
            res.append("No")
    
    for ans in res:
        print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.