Overview

If we consider only mountains with height \(X\) or above as “active,” the problem asks us to compute the sum of the maximum \(B\) values for each contiguous interval of active mountains.
Rather than rebuilding everything for each query, we can process queries in decreasing order of \(X\), adding mountains one by one and managing connected component information with a DSU (Union-Find) for an efficient solution.

Analysis

The difficulty of this problem lies in the fact that the “visible mountains (\(A_i \ge X\))” change with each query, and the evaluation value is determined by:

• Each contiguous interval (connected component)
• The maximum \(B\) value within that interval

Why a naive solution is too slow

For each query, if we: 1. Check which \(A_i \ge X\) 2. Enumerate contiguous intervals 3. Take the maximum \(B\) in each interval

this results in \(O(NQ)\) in the worst case, which is too slow for \(N+Q \le 2\times10^5\).

Key Insight

If we process queries in decreasing order of \(X\), as the threshold decreases, only “newly visible mountains” are added (none are ever removed).
This means we only need to handle “mountain additions,” which pairs well with Union-Find.

• When mountain \(i\) is added, it initially forms a single-element component (with scenic value \(B_i\))
• If adjacent neighbors (left or right) are already active, merge the components
• The scenic value of a component is “the maximum \(B\) within the component”

When merging components:
Subtract the contributions of the two components before merging, then add the contribution of the merged component
This allows us to maintain the overall sum at all times.

Algorithm

1. Sort mountains as \((A_i, i)\) in decreasing order of \(A_i\).
2. Sort queries as \((X_j, j)\) in decreasing order of \(X_j\) (\(j\) is used to restore the original order).
3. Maintain active[i] (whether mountain \(i\) is active).
4. For each connected component in the Union-Find, manage:
   • Parent parent
   • Size sz (for union by size)
   • Maximum beauty within the component compMax
5. ansSum = current “sum of scenic values.”
6. For each query \(X\) (in decreasing order):
   • Add all not-yet-added mountains with \(A_i \ge X\)
   • Upon addition: ansSum += B_i
   • If left or right neighbors are active, call unite
     • In unite(x, y):

          - `ansSum -= compMax[root_x]`
          - `ansSum -= compMax[root_y]`
          - Merge and set `compMax = max(...)`
          - `ansSum += new_compMax`
       

   • The current ansSum is the answer for this query
7. Output answers in the original query order.

Complexity

• Time complexity: \(O((N+Q)\log(N+Q))\) (mainly due to sorting; Union-Find operations are amortized nearly constant)
• Space complexity: \(O(N+Q)\)

Implementation Notes

• Creating active with length N+2 as a sentinel simplifies boundary handling for idx-1 and idx+1.

• Use path compression for find and union by size for unite to ensure speed.

• Since queries are reordered, make sure to save the “original index” to place answers back correctly.

• ansSum can become large, so use long long.

  Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<int> A(N + 2, 0), B(N + 2, 0);
    for (int i = 1; i <= N; i++) {
        cin >> A[i] >> B[i];
    }

    vector<pair<int,int>> mountains; // (A, idx)
    mountains.reserve(N);
    for (int i = 1; i <= N; i++) mountains.push_back({A[i], i});
    sort(mountains.begin(), mountains.end(), [&](auto &x, auto &y){
        return x.first > y.first;
    });

    vector<pair<int,int>> queries; // (X, qidx)
    queries.reserve(Q);
    for (int i = 0; i < Q; i++) {
        int x; cin >> x;
        queries.push_back({x, i});
    }
    sort(queries.begin(), queries.end(), [&](auto &x, auto &y){
        return x.first > y.first;
    });

    vector<char> active(N + 2, 0);
    long long ansSum = 0;

    auto seg_value = [&](int l, int r) -> int {
        int mx = 0;
        for (int i = l; i <= r; i++) mx = max(mx, B[i]);
        return mx;
    };

    // To make it O((N+Q)logN), use DSU + multisets of candidates for segment maxima by merge.
    // But segment max by B over contiguous active runs requires efficient dynamic connectivity with max.
    // We can do this with DSU where each component stores max B.
    // Activation only adds nodes and unions neighbors.

    vector<int> parent(N + 2), sz(N + 2), compMax(N + 2, 0);
    iota(parent.begin(), parent.end(), 0);
    for (int i = 1; i <= N; i++) {
        sz[i] = 1;
        compMax[i] = B[i];
    }

    function<int(int)> findp = [&](int x)->int{
        if (parent[x] == x) return x;
        return parent[x] = findp(parent[x]);
    };

    auto unite = [&](int x, int y) {
        x = findp(x); y = findp(y);
        if (x == y) return;
        // removing two components contribution
        ansSum -= compMax[x];
        ansSum -= compMax[y];
        if (sz[x] < sz[y]) swap(x, y);
        parent[y] = x;
        sz[x] += sz[y];
        compMax[x] = max(compMax[x], compMax[y]);
        // adding merged component contribution
        ansSum += compMax[x];
    };

    vector<long long> ans(Q);
    int p = 0; // pointer for mountains sorted by A desc

    for (auto &[X, qi] : queries) {
        while (p < N && mountains[p].first >= X) {
            int idx = mountains[p].second;
            active[idx] = 1;
            // new single component contributes
            ansSum += B[idx];

            if (active[idx - 1]) unite(idx, idx - 1);
            if (active[idx + 1]) unite(idx, idx + 1);

            p++;
        }
        ans[qi] = ansSum;
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.