Overview

Mountain huts are arranged in a straight line, and a connecting path exists between adjacent huts if their elevation difference is at most \(K\). For multiple queries, we need to determine whether two specified mountain huts belong to the same connected component (area).

Analysis

In this problem, we first consider what it means to “belong to the same area.” This means that there exists a chain of connecting paths between the two mountain huts. In other words, if all adjacent pairs of huts between them are connected by paths, they belong to the same area.

For example, for hut 1 and hut 4 to belong to the same area: - There must be a connecting path between huts 1 and 2, - There must be a connecting path between huts 2 and 3, - There must be a connecting path between huts 3 and 4.

In other words, we just need to check whether all adjacent pairs within the interval \([L, R]\) have connecting paths.

A naive approach would be to check each adjacent pair within the interval one by one for every query, but in the worst case this results in \(O(NQ)\) time complexity, which may not finish within the time limit (TLE) given the large constraints.

Therefore, we preprocess the data so that we can quickly compute “the number of connecting paths within an interval.” Specifically, we maintain an array indicating whether a connecting path exists between each pair of adjacent huts, and precompute its prefix sum. This allows us to determine the number of connecting paths in any interval in \(O(1)\).

Algorithm

1. For each pair of adjacent huts, determine whether their elevation difference is at most \(K\). Record 1 if a connecting path exists and 0 otherwise in an array connected.
2. Compute the prefix sum of connected to create the prefix_sum array. This allows us to find the number of connecting paths within any interval \([L, R]\) in \(O(1)\).
3. For each query:
   • The number of adjacent pairs contained in the interval \([L, R]\) is \(R - L\).
   • If the number of connecting paths within this interval equals \(R - L\), then all adjacent pairs have connecting paths, so output Yes. Otherwise, output No.

Concrete Example

Sample input:

5 3 2
1 4 6 9 7
1 3
2 5

• Hut elevations: \([1, 4, 6, 9, 7]\)
• Absolute differences between adjacent huts: \([3, 2, 3, 2]\)
• All are at most \(K=3\), so all adjacent pairs have connecting paths.
• connected = [1, 1, 1, 1]
• Prefix sum: prefix_sum = [0, 1, 2, 3, 4]

Query 1: Huts 1 and 3 → number of pairs = 2, number of paths = prefix_sum[2] - prefix_sum[0] = 2 → Yes Query 2: Huts 2 and 5 → number of pairs = 3, number of paths = prefix_sum[4] - prefix_sum[1] = 3 → Yes

Complexity

• Time complexity: \(O(N + Q)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since the input is given in 1-indexed format, it needs to be converted to 0-indexed for internal processing.

• Adding 0 at the beginning of the prefix sum simplifies the interval sum calculation.

• sys.stdin.read is used to read large amounts of input efficiently.

  Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    Q = int(data[2])
    
    A = list(map(int, data[3:3+N]))
    
    # 隣接する山小屋間に連絡路があるかをチェック
    connected = [0] * (N - 1)
    for i in range(N - 1):
        if abs(A[i] - A[i+1]) <= K:
            connected[i] = 1
    
    # 接頭和を計算して、任意の区間での連絡路の数をO(1)で取得できるようにする
    prefix_sum = [0] + list(accumulate(connected))
    
    # 各質問に対して処理
    results = []
    index = 3 + N
    for _ in range(Q):
        L = int(data[index]) - 1  # 0-indexedにする
        R = int(data[index+1]) - 1
        index += 2
        
        # 区間[L, R)に含まれる連絡路の数
        links = prefix_sum[R] - prefix_sum[L]
        
        # [L, R]の間の隣接ペアの数
        total_pairs = R - L
        
        # すべての隣接ペアが連絡路を持つ場合、同じエリアに属する
        if links == total_pairs:
            results.append("Yes")
        else:
            results.append("No")
    
    print("\n".join(results))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.