概要

雲の高さ \(X\) ごとに、標高 \(A_i \geq X\) の山だけを見えるものとして、連続して見える区間ごとの美しさ最大値の合計を求める問題です。

雲の高さを高い順に処理すると、見える山は増えていくだけなので、Union-Find を使って連続区間を管理できます。

考察

ある雲の高さ \(X\) に対して見える山は、条件 \(A_i \geq X\) を満たす山です。

見えている山を番号順に見ると、隣り合って見えている山同士は同じ山脈に属します。
つまり、見えている山を「有効なマス」と考えると、山脈は有効なマスの連結成分です。

例えば、見えている山が次のような状態だとします。

番号:  1 2 3 4 5 6 7 8
状態:  × ○ ○ ○ × × ○ ○

このとき山脈は、

• \(2,3,4\)
• \(7,8\)

の \(2\) つです。

それぞれの山脈について \(B_i\) の最大値を取り、その合計を求めます。

---

素朴に各クエリごとに全ての山を確認すると、\(O(NQ)\) かかります。

制約では \(N+Q \leq 2 \times 10^5\) なので、最悪で非常に大きくなり、TLE します。

---

ここで重要な観察は、雲の高さ \(X\) を高い順に処理することです。

雲の高さを下げていくと、見える山は増えることはあっても消えることはありません。

つまり、

• 最初は何も見えていない
• \(X\) を下げる
• 新しく条件 \(A_i \geq X\) を満たす山を追加する
• 隣の山がすでに見えていれば、山脈を結合する

という流れで処理できます。

この「隣り合う区間を結合する」処理には Union-Find が適しています。

アルゴリズム

山とクエリをそれぞれ降順に並べます。

• 山: 標高 \(A_i\) が高い順
• クエリ: 雲の高さ \(X_j\) が高い順

そして、クエリを高い順に処理します。

現在の雲の高さを \(X\) とすると、まだ追加していない山のうち \(A_i \geq X\) を満たす山をすべて追加します。

山 \(i\) を追加するときは、まずその山だけの山脈を作ります。

このとき、その山脈の眺望値は \(B_i\) なので、全体の答え total に \(B_i\) を足します。

次に、左隣 \(i-1\) や右隣 \(i+1\) がすでに見えているなら、それらは同じ山脈になるので Union-Find で結合します。

---

Union-Find の各連結成分に対して、以下を管理します。

• その成分が表す山脈
• その山脈内の美しさの最大値

ある 2 つの山脈を結合するとします。

結合前の眺望値への寄与は、

\(mx_1 + mx_2\)

です。

結合後は 1 つの山脈になるので、寄与は、

\(\max(mx_1, mx_2)\)

になります。

したがって、全体の合計 total は次のように更新できます。

1. 結合前の寄与 \(mx_1 + mx_2\) を引く
2. 結合後の寄与 \(\max(mx_1, mx_2)\) を足す

これにより、常に total が現在の眺望値の総和になります。

---

クエリは降順に並べ替えて処理しますが、出力は入力された順番で行う必要があります。

そのため、各クエリに元の番号を持たせておき、答えを ans[元の番号] に保存します。

計算量

• 時間計算量: \(O((N+Q)\log(N+Q))\)
• 空間計算量: \(O(N+Q)\)

山とクエリのソートに \(O((N+Q)\log(N+Q))\) かかります。

Union-Find の操作はほぼ定数時間で、全体で \(O(N \alpha(N))\) 程度です。
ここで \(\alpha(N)\) は逆アッカーマン関数で、実用上はほぼ定数です。

実装のポイント

• parent[i] = -1 のとき、山 \(i\) はまだ見えていない状態として扱います。

• 山を追加するときに parent[i] = i として Union-Find に登録します。

• 追加した山の左右がすでに見えていれば unite します。

• unite では、結合前後で total を正しく更新します。

• クエリを並べ替えるため、元のクエリ番号を一緒に持っておきます。

  ソースコード

import sys

input = sys.stdin.readline

N, Q = map(int, input().split())

mountains = []
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    mountains.append((a, i, b))
    B[i] = b

queries = []
for j in range(Q):
    x = int(input())
    queries.append((x, j))

mountains.sort(reverse=True)
queries.sort(reverse=True)

parent = [-1] * N
size = [1] * N
mx = [0] * N
ans = [0] * Q

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def unite(x, y, total):
    rx = find(x)
    ry = find(y)
    if rx == ry:
        return total

    if size[rx] < size[ry]:
        rx, ry = ry, rx

    total -= mx[rx] + mx[ry]
    parent[ry] = rx
    size[rx] += size[ry]
    if mx[ry] > mx[rx]:
        mx[rx] = mx[ry]
    total += mx[rx]

    return total

total = 0
p = 0

for x, qi in queries:
    while p < N and mountains[p][0] >= x:
        _, idx, b = mountains[p]
        parent[idx] = idx
        mx[idx] = b
        total += b

        if idx > 0 and parent[idx - 1] != -1:
            total = unite(idx, idx - 1, total)
        if idx + 1 < N and parent[idx + 1] != -1:
            total = unite(idx, idx + 1, total)

        p += 1

    ans[qi] = total

print("\n".join(map(str, ans)))

---

この解説は gpt-5.5-high によって生成されました。