Overview

Given a cloud height \(X\), this problem asks us to find the maximum beauty value for each contiguous interval (mountain range) formed by mountains with elevation \(X\) or higher, and compute the total sum. We solve this efficiently using offline processing and Union-Find.

Analysis

Problems with the Naive Approach

If we enumerate visible mountains for each query, split them into contiguous intervals, and find the maximum for each, it costs \(O(N)\) per query, resulting in \(O(NQ)\) overall, which will TLE given the constraints.

Key Insight

We consider processing queries offline. If we process cloud heights \(X\) from largest to smallest, as \(X\) decreases, visible mountains only increase (once a mountain becomes visible, it never disappears) — this gives us monotonicity.

When a new mountain \(i\) becomes visible: - Mountain \(i\) forms a new mountain range by itself, and its scenic value \(B_i\) is added to the total sum. - If an adjacent mountain (\(i-1\) or \(i+1\)) is already visible, the mountain ranges merge.

Change in Scenic Value When Mountain Ranges Merge

Consider the case where two mountain ranges merge. If their respective scenic values before merging are \(m_1, m_2\), their contribution to the total sum before merging is \(m_1 + m_2\), and after merging it becomes \(\max(m_1, m_2)\). Therefore, the decrease in the total sum is:

\[m_1 + m_2 - \max(m_1, m_2) = \min(m_1, m_2)\]

Algorithm

1. Sort mountains in descending order of elevation, and sort queries in descending order of \(X\).
2. Prepare a Union-Find (DSU), managing the maximum beauty max_beauty for each connected component.
3. Process queries from largest \(X\) first. Before each query, sequentially add mountains with elevation \(\geq X\):
   • When adding mountain \(i\): total += B[i]
   • If left neighbor \(i-1\) is already visible, merge them: total -= min(max_beauty[root_i], max_beauty[root_{i-1}])
   • If right neighbor \(i+1\) is already visible, merge similarly
4. The answer for each query is the current value of total.

Concrete Example

If mountains are \((A, B) = (5, 10), (3, 20), (4, 5), (6, 8)\) and \(X = 4\): - Mountains with elevation \(\geq 4\): mountain 1 (elevation 5), mountain 3 (elevation 4), mountain 4 (elevation 6) - Visible mountain indices: {1, 3, 4} → mountain ranges {1} and {3, 4} - Sum of scenic values: \(B_1 + \max(B_3, B_4) = 10 + 8 = 18\)

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Sorting: \(O(N \log N + Q \log Q)\)
  • Each Union-Find operation is nearly \(O(1)\) (with path compression)
  • Total number of merges is at most \(2N\)
• Space complexity: \(O(N + Q)\)

Implementation Notes

• Offline processing: Since we process queries in a different order, we store the original indices and rearrange the output at the end.

• Return value of Union-Find’s merge function: By having it return the decrease in total sum \(\min(m_1, m_2)\) due to merging, updating total can be written concisely.

• visible array: Manages whether a mountain has already been added, used for determining whether to merge with adjacent mountains.

• Pointer (ptr) technique: By arranging mountains in descending order of elevation and advancing a pointer, we add only the necessary mountains for each query (a two-pointer-like approach).

  Source Code

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, rank_;
    vector<long long> max_beauty;
    
    DSU(int n) : parent(n), rank_(n, 0), max_beauty(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    
    long long merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return 0;
        long long decrease = min(max_beauty[x], max_beauty[y]);
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        max_beauty[x] = max(max_beauty[x], max_beauty[y]);
        if (rank_[x] == rank_[y]) rank_[x]++;
        return decrease;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q;
    cin >> N >> Q;
    
    vector<int> A(N);
    vector<long long> B(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }
    
    vector<long long> X(Q);
    for (int j = 0; j < Q; j++) {
        cin >> X[j];
    }
    
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return A[a] > A[b];
    });
    
    vector<int> qorder(Q);
    iota(qorder.begin(), qorder.end(), 0);
    sort(qorder.begin(), qorder.end(), [&](int a, int b) {
        return X[a] > X[b];
    });
    
    DSU dsu(N);
    vector<bool> visible(N, false);
    long long total = 0;
    int ptr = 0;
    
    vector<long long> ans(Q);
    
    for (int qi = 0; qi < Q; qi++) {
        int j = qorder[qi];
        long long x = X[j];
        
        while (ptr < N && A[order[ptr]] >= x) {
            int i = order[ptr];
            visible[i] = true;
            dsu.max_beauty[i] = B[i];
            total += B[i];
            
            if (i > 0 && visible[i-1]) {
                total -= dsu.merge(i, i-1);
            }
            if (i < N-1 && visible[i+1]) {
                total -= dsu.merge(i, i+1);
            }
            
            ptr++;
        }
        
        ans[j] = total;
    }
    
    for (int j = 0; j < Q; j++) {
        cout << ans[j] << "\n";
    }
    
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.