Overview

For each cloud height \(X\), considering only mountains with elevation \(A_i \geq X\) as visible, we need to find the sum of maximum beauty values for each contiguous visible interval.

By processing cloud heights in decreasing order, visible mountains only increase, so we can manage contiguous intervals using Union-Find.

Analysis

For a given cloud height \(X\), the visible mountains are those satisfying the condition \(A_i \geq X\).

Looking at the visible mountains in order of their indices, adjacent visible mountains belong to the same mountain range.
In other words, if we consider visible mountains as “active cells,” mountain ranges are connected components of active cells.

For example, suppose the visible mountains are in the following state:

Index:  1 2 3 4 5 6 7 8
State:  × ○ ○ ○ × × ○ ○

In this case, the mountain ranges are:

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

giving \(2\) ranges.

For each mountain range, we take the maximum of \(B_i\) and sum them up.

---

Naively checking all mountains for each query costs \(O(NQ)\).

Given the constraint \(N+Q \leq 2 \times 10^5\), this can become extremely large in the worst case and will result in TLE.

---

The key observation here is to process cloud heights in decreasing order.

As the cloud height decreases, visible mountains can only increase and never disappear.

That is, we can process as follows:

• Initially nothing is visible
• Decrease \(X\)
• Add mountains that newly satisfy \(A_i \geq X\)
• If a neighboring mountain is already visible, merge the mountain ranges

The operation of “merging adjacent intervals” is well-suited for Union-Find.

Algorithm

Sort the mountains and queries in decreasing order respectively.

• Mountains: in decreasing order of elevation \(A_i\)
• Queries: in decreasing order of cloud height \(X_j\)

Then, process queries in decreasing order.

For the current cloud height \(X\), add all mountains that have not been added yet and satisfy \(A_i \geq X\).

When adding mountain \(i\), first create a mountain range containing only that mountain.

At this point, the scenic value of this range is \(B_i\), so add \(B_i\) to the overall answer total.

Next, if the left neighbor \(i-1\) or right neighbor \(i+1\) is already visible, they belong to the same mountain range, so merge them using Union-Find.

---

For each connected component in Union-Find, we maintain:

• The mountain range represented by that component
• The maximum beauty value within that range

Suppose we merge two mountain ranges.

The contribution to the scenic value before merging is:

\(mx_1 + mx_2\)

After merging, it becomes one mountain range, so the contribution is:

\(\max(mx_1, mx_2)\)

Therefore, the overall sum total can be updated as follows:

1. Subtract the pre-merge contribution \(mx_1 + mx_2\)
2. Add the post-merge contribution \(\max(mx_1, mx_2)\)

This ensures that total always equals the current sum of scenic values.

---

Queries are sorted in decreasing order for processing, but output must be in the original input order.

Therefore, we attach the original index to each query and store the answer in ans[original index].

Complexity

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

Sorting mountains and queries takes \(O((N+Q)\log(N+Q))\).

Union-Find operations are nearly constant time, totaling \(O(N \alpha(N))\).
Here \(\alpha(N)\) is the inverse Ackermann function, which is practically constant.

Implementation Notes

• When parent[i] = -1, mountain \(i\) is treated as not yet visible.

• When adding a mountain, set parent[i] = i to register it in the Union-Find.

• If the left or right neighbor of the added mountain is already visible, call unite.

• In unite, correctly update total before and after merging.

• Since queries are reordered, keep track of the original query index alongside each query.

  Source Code

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

---

This editorial was generated by gpt-5.5-high.