概要

隣接する山小屋の標高差が\(K\)以下なら連絡路があるとき、複数の質問に対して指定された2つの山小屋が同じエリアに属するか判定する問題です。

考察

素朴なアプローチでは、各質問に対してBFSやDFSで連結性を調べると、最悪ケースで\(O(NQ)\)の時間がかかり、制約条件\(N, Q \leq 2 \times 10^5\)では到底間に合いません。そこで、事前に全てのエリアを特定しておき、各質問では同じエリアに属するかだけを確認すればよいことに気づきます。

重要な観察は、連絡路が隣接する山小屋間のみに存在するため、エリアは連続した区間になるということです。ただし、必ずしも連続した区間とは限らない点に注意が必要です（例えば、標高差が\(K\)以下でない箇所でエリアが分断されます）。

アルゴリズム

Union-Find（Disjoint Set Union, DSU）データ構造を使用します。隣接するすべての山小屋の組\((i, i+1)\)について、標高差の絶対値が\(K\)以下であればunion操作で結合します。これにより、同じエリアに属する山小屋は同じ木（連結成分）に属するようになります。

各質問では、\(L_j\)と\(R_j\)が同じ木に属するかどうかをfind操作で確認します。同じ木に属していればYes、異なればNoを出力します。

計算量

• 時間計算量: \(O(N \alpha(N) + Q \alpha(N))\)
  • Union-Findの操作はアッカーマン関数の逆関数\(\alpha(N)\)を定数と見なせるため、ほぼ線形時間
• 空間計算量: \(O(N)\)
  • 親配列とランク配列のため

実装のポイント

• Union-Findの経路圧縮とランクによる union を実装することで効率化
• 入力の山小屋番号は1-indexedなので、0-indexedに変換
• 隣接する山小屋の組のみをチェックすれば十分（エリアの連続性）
• 大規模な入力に対応するため、sys.stdin.read()で一括読み込み

ソースコード

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

この解説は deepseekv3 によって生成されました。