概要

雲の高さ \(X\) 以上の山だけを「有効」とすると、有効な山の連続区間ごとに \(B\) の最大値を足したものを求める問題です。
クエリごとに毎回作り直すのではなく、\(X\) を大きい順に処理して山を1つずつ追加し、連結成分の情報を DSU（Union-Find）で管理すると高速に解けます。

考察

この問題の難しさは、「見えている山（\(A_i \ge X\)）」がクエリごとに変わることと、評価値が

• 連続区間ごと（連結成分ごと）
• その区間内の \(B\) の最大値

で決まる点です。

素朴解が難しい理由

各クエリごとに
1. \(A_i \ge X\) を判定
2. 連続区間を列挙
3. 各区間の最大 \(B\) を取る
をすると、最悪で \(O(NQ)\) になり、\(N+Q \le 2\times10^5\) では間に合いません。

重要な気づき

クエリを \(X\) の降順で見ると、しきい値が下がるにつれて「新たに見える山」が増えるだけです（消えることはない）。
つまり「山の追加」だけを扱えばよく、これは Union-Find と相性が良いです。

• 山 \(i\) が追加されたとき、最初は1点の成分（眺望値は \(B_i\)）
• 左右の隣がすでに有効なら成分を結合
• 成分の眺望値は「成分内の \(B\) 最大」

成分を結合するときは、
結合前の2成分の寄与を引いて、結合後の寄与を足す
とすれば、全体の総和を常に更新できます。

アルゴリズム

1. 山を \((A_i, i)\) として \(A_i\) 降順にソート。
2. クエリを \((X_j, j)\) として \(X_j\) 降順にソート（\(j\) は元の順番復元用）。
3. active[i]（山 \(i\) が有効か）を持つ。
4. Union-Find の各連結成分に対して以下を管理：
   • 親 parent
   • サイズ sz（union by size 用）
   • 成分内最大美しさ compMax
5. ansSum = 現在の「眺望値の総和」。
6. 各クエリ \(X\)（降順）について：
   • まだ追加していない山のうち \(A_i \ge X\) をすべて追加
   • 追加時に ansSum += B_i
   • 左右の隣が active なら unite
     • unite(x,y) では

          - `ansSum -= compMax[root_x]`
          - `ansSum -= compMax[root_y]`
          - 併合して `compMax = max(...)`
          - `ansSum += new_compMax`
       

   • この時点の ansSum がそのクエリの答え
7. 元のクエリ順に出力。

計算量

• 時間計算量: \(O((N+Q)\log(N+Q))\)（主にソート。Union-Find は償却ほぼ定数）
• 空間計算量: \(O(N+Q)\)

実装のポイント

• 番兵的に active を N+2 長で作ると、idx-1, idx+1 の境界処理が楽です。

• Union-Find の find は経路圧縮、unite はサイズ併合にすると高速。

• クエリを並べ替えるので、必ず「元のインデックス」を保存して答えを戻すこと。

• ansSum は最大で大きくなるため long long を使います。

  ソースコード

#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;
}

---

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