Overview

As the cloud height \(X\) changes, the visible mountains (those with elevation \(A_i \geq X\)) change. The problem asks us to find the sum of the maximum beauty \(B_i\) for each group of consecutive visible mountains (mountain ranges). This can be solved efficiently by combining “offline queries” that process cloud heights in descending order with “Union-Find (disjoint set data structure)” to merge adjacent mountains.

Analysis

1. Naive Approach and Its Limitations

For each query \(X_j\), if we scan all mountains to identify mountain ranges and compute the maximum for each, it takes \(O(N)\) per query. With \(Q\) queries in total, this becomes \(O(NQ)\), which does not fit within the time limit for the given constraints (\(N, Q \leq 2 \times 10^5\)).

2. Focusing on Changes in Cloud Height

Imagine the cloud height \(X\) gradually decreasing from a high value. - As \(X\) decreases, new mountains may become visible, but once a mountain is visible, it never becomes hidden again. - When a new mountain becomes visible, if its left or right neighbors are already visible, they connect to form a single “mountain range.”

This property of “elements being added and adjacent groups being merged” can be efficiently managed with a Union-Find data structure.

3. Offline Queries

Instead of answering queries in their original order, we sort them by cloud height \(X_j\) in descending order and process them. This way, by simply “activating” mountains in order from highest elevation, we can handle all queries in a single pass.

Algorithm

1. Preparation:
   • Sort the mountain information in descending order of elevation \(A_i\).
   • Sort queries in descending order of cloud height \(X_j\) (while keeping track of their original order).
   • Prepare a Union-Find that can maintain the maximum beauty for each group (mountain range).
2. Processing Queries:
   • For each query \(X_j\), activate all mountains that have not yet been activated and satisfy \(A_i \geq X_j\).
   • Mountain activation procedure:
     1. Mark mountain \(i\) as “active” and add \(B_i\) to the running total of scenic values.
     2. If the left neighbor mountain \(i-1\) is active, merge them using Union-Find. At this point, subtract the maximum beauty of each group before merging from the total, and add the new group’s maximum beauty (the larger of the two groups’ maximums) to the total.
     3. Perform the same merging process for the right neighbor mountain \(i+1\).
3. Output Answers:
   • After processing all queries, output the results in the original query order.

Complexity

• Time Complexity: \(O(N \log N + Q \log Q)\)
  • Sorting mountains and queries takes \(O(N \log N + Q \log Q)\).
  • Union-Find operations are nearly constant time \(O(\alpha(N))\), and since each mountain is activated exactly once, the total is \(O((N+Q) \alpha(N))\).
• Space Complexity: \(O(N + Q)\)
  • Required for storing arrays for mountains, queries, and Union-Find.

Implementation Notes

• Extended Union-Find: A standard Union-Find only manages group connectivity, but here we also maintain the “maximum beauty \(B_i\)” within each group at the root node.

• Incremental Total Updates: By incrementally updating the overall “sum of scenic values” each time a mountain is added or groups are merged, we can obtain the answer for each query in \(O(1)\).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem: Mountain View (山脈の眺望)
 * 
 * Approach:
 * 1. Mountains are visible if height A_i >= cloud height X.
 * 2. Visible mountains form contiguous segments (mountain ranges).
 * 3. Each range's view value is the maximum beauty B_i in that range.
 * 4. We need to find the sum of these view values for multiple queries of X.
 * 
 * Strategy:
 * - Sort both mountains and queries by height (A_i and X_j) in descending order.
 * - As X_j decreases, more mountains become visible.
 * - Use a Disjoint Set Union (DSU) to maintain the contiguous ranges of visible mountains.
 * - For each range, store the maximum beauty value B_i.
 * - Update the total sum of view values as mountains are added and ranges are merged.
 * 
 * Time Complexity: O(N log N + Q log Q) due to sorting. DSU operations are nearly constant time.
 * Space Complexity: O(N + Q) to store mountain data, query data, and DSU structures.
 */

struct Mountain {
    int id;
    int a;
    int b;
};

struct Query {
    int id;
    int x;
};

// Global arrays for DSU and state tracking
int parent[200010];
long long max_b_val[200010];
bool active[200010];
long long current_sum = 0;

// Iterative find_set with path compression to avoid recursion limits
int find_set(int v) {
    int root = v;
    while (root != parent[root])
        root = parent[root];
    while (v != root) {
        int next = parent[v];
        parent[v] = root;
        v = next;
    }
    return root;
}

// Activate a mountain when it becomes visible and merge adjacent visible ranges
void activate(int i, int n, const vector<int>& b) {
    active[i] = true;
    long long current_max = b[i];
    parent[i] = i;

    // Check if the mountain to the left is already visible
    if (i > 0 && active[i - 1]) {
        int root_l = find_set(i - 1);
        current_sum -= max_b_val[root_l];
        if (max_b_val[root_l] > current_max) current_max = max_b_val[root_l];
        parent[root_l] = i; // Merge the left range into the new mountain's set
    }

    // Check if the mountain to the right is already visible
    if (i < n - 1 && active[i + 1]) {
        int root_r = find_set(i + 1);
        current_sum -= max_b_val[root_r];
        if (max_b_val[root_r] > current_max) current_max = max_b_val[root_r];
        parent[root_r] = i; // Merge the right range into the new mountain's set
    }

    // Update the maximum beauty for the merged range and add it to the total sum
    max_b_val[i] = current_max;
    current_sum += current_max;
}

int main() {
    // Speed up I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<Mountain> mountains(n);
    vector<int> b_vals(n);
    for (int i = 0; i < n; ++i) {
        mountains[i].id = i;
        cin >> mountains[i].a >> mountains[i].b;
        b_vals[i] = mountains[i].b;
    }

    vector<Query> queries(q);
    for (int i = 0; i < q; ++i) {
        queries[i].id = i;
        cin >> queries[i].x;
    }

    // Sort mountains by altitude A_i descending
    sort(mountains.begin(), mountains.end(), [](const Mountain& a, const Mountain& b) {
        if (a.a != b.a) return a.a > b.a;
        return a.id < b.id;
    });

    // Sort queries by cloud height X_j descending
    vector<Query> sorted_queries = queries;
    sort(sorted_queries.begin(), sorted_queries.end(), [](const Query& a, const Query& b) {
        if (a.x != b.x) return a.x > b.x;
        return a.id < b.id;
    });

    vector<long long> results(q);
    int k = 0;
    // Process queries in descending order of cloud height
    for (int i = 0; i < q; ++i) {
        // Activate all mountains that are visible at the current cloud height
        while (k < n && mountains[k].a >= sorted_queries[i].x) {
            activate(mountains[k].id, n, b_vals);
            k++;
        }
        // Store result for the original query index
        results[sorted_queries[i].id] = current_sum;
    }

    // Output all query results
    for (int i = 0; i < q; ++i) {
        cout << results[i] << "\n";
    }

    return 0;
}

This editorial was generated by gemini-3-flash-thinking.