概要

雲の高さ \(X\) ごとに、標高 \(A_i \geq X\) の山だけが見えます。
見えている連続区間ごとに美しさ \(B_i\) の最大値を取り、それらの合計を各クエリについて求めます。

考察

ある雲の高さ \(X\) に対して、見える山は \(A_i \geq X\) を満たす山です。

素朴には、各クエリごとに全ての山を左から見て、見えている連続区間を調べれば答えを求められます。
しかし、これは \(1\) クエリあたり \(O(N)\) かかるため、全体で \(O(NQ)\) となります。
\(N+Q \leq 2 \times 10^5\) なので、これは間に合いません。

ここで重要な気づきは、雲の高さを高い方から低い方へ見ていくと、見える山は増えるだけで、消えることはないという点です。

例えば、雲の高さを下げると、新しく見える山が追加されます。
新しく追加された山は、左右の山がすでに見えていれば、それらの山脈とつながります。

つまり、次のように管理できます。

• 見えている山を「有効」とする
• 隣り合う有効な山同士を同じ連結成分として扱う
• 各連結成分が 1 つの山脈に対応する
• 各連結成分について、美しさ \(B_i\) の最大値を持つ
• 答えは、全連結成分の最大値の合計

これは Union-Find（DSU）で効率よく管理できます。

アルゴリズム

クエリを雲の高さ \(X\) の降順に処理します。
また、山も標高 \(A_i\) の降順に並べておきます。

現在処理しているクエリの雲の高さを \(X\) とすると、まだ追加していない山のうち \(A_i \geq X\) のものをすべて追加します。

山 \(i\) を追加するときは、次の処理をします。

1. 山 \(i\) を有効化する
2. 山 \(i\) 単体で新しい山脈になるので、答えの合計 total に \(B_i\) を足す
3. 左隣 \(i-1\) が有効なら Union-Find で結合する
4. 右隣 \(i+1\) が有効なら Union-Find で結合する

山脈同士を結合するとき、もともとの山脈の眺望値をそれぞれ \(m_1, m_2\) とすると、結合後の眺望値は

\( \max(m_1, m_2) \)

です。

したがって、total は次のように更新します。

\( total \leftarrow total - m_1 - m_2 + \max(m_1, m_2) \)

Union-Find の各連結成分に対して、その成分内の \(B_i\) の最大値を持たせておけば、この更新が高速にできます。

クエリは降順に処理していますが、出力は入力順に行う必要があります。
そのため、クエリには元の番号を持たせておき、答えを ans[元の番号] に保存します。

計算量

• 時間計算量: \(O((N+Q)\log(N+Q))\)
  • 山とクエリのソートに \(O(N\log N + Q\log Q)\)
  • Union-Find の操作はほぼ \(O(1)\)
• 空間計算量: \(O(N+Q)\)

実装のポイント

Union-Find では、各連結成分について次の情報を持ちます。

• parent: 親
• sz: 成分サイズ
• mx: その成分内の美しさ \(B_i\) の最大値

山を追加するときは、まず単独の成分として

dsu.mx[idx] = B[idx];
total += B[idx];

とします。

その後、左右の山がすでに有効なら結合します。

if (idx > 0 && active[idx - 1]) {
    dsu.unite(idx, idx - 1, total);
}
if (idx + 1 < N && active[idx + 1]) {
    dsu.unite(idx, idx + 1, total);
}

結合時には、total から結合前の 2 成分の最大値を引き、結合後の最大値を足すことが重要です。

また、条件は \(A_i \geq X\) なので、山を追加する判定は

mountains[ptr].first >= X

になります。

ソースコード

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

struct DSU {
    vector<int> parent, sz;
    vector<long long> mx;

    DSU(int n) : parent(n), sz(n, 1), mx(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    void unite(int a, int b, long long &total) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return;

        total -= mx[ra];
        total -= mx[rb];

        if (sz[ra] < sz[rb]) swap(ra, rb);
        parent[rb] = ra;
        sz[ra] += sz[rb];
        mx[ra] = max(mx[ra], mx[rb]);

        total += mx[ra];
    }
};

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

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

    vector<long long> A(N), B(N);
    vector<pair<long long, int>> mountains(N);

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

    vector<pair<long long, int>> queries(Q);
    for (int i = 0; i < Q; i++) {
        long long X;
        cin >> X;
        queries[i] = {X, i};
    }

    sort(mountains.begin(), mountains.end(), greater<>());
    sort(queries.begin(), queries.end(), greater<>());

    DSU dsu(N);
    vector<bool> active(N, false);
    vector<long long> ans(Q);

    long long total = 0;
    int ptr = 0;

    for (auto [X, qi] : queries) {
        while (ptr < N && mountains[ptr].first >= X) {
            int idx = mountains[ptr].second;

            active[idx] = true;
            dsu.parent[idx] = idx;
            dsu.sz[idx] = 1;
            dsu.mx[idx] = B[idx];

            total += B[idx];

            if (idx > 0 && active[idx - 1]) {
                dsu.unite(idx, idx - 1, total);
            }
            if (idx + 1 < N && active[idx + 1]) {
                dsu.unite(idx, idx + 1, total);
            }

            ptr++;
        }

        ans[qi] = total;
    }

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

    return 0;
}

---

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