概要

雲の高さ \(X\) が変化するにつれて見える山（標高 \(A_i \geq X\)）が変化する中で、連続する山のグループ（山脈）ごとの最大美しさ \(B_i\) の合計を求める問題です。雲の高さを降順に処理する「オフラインクエリ」と、隣接する山を統合する「Union-Find（素集合データ構造）」を組み合わせることで効率的に解くことができます。

考察

1. 素朴なアプローチとその限界

各クエリ \(X_j\) に対して、すべての山を走査して山脈を特定し、それぞれの最大値を計算すると、1つのクエリに \(O(N)\) かかります。クエリ数が \(Q\) 個あるため、全体で \(O(NQ)\) となり、今回の制約（\(N, Q \leq 2 \times 10^5\)）では実行時間制限に間に合いません。

2. 雲の高さの変化に注目する

雲の高さ \(X\) が高い状態から徐々に低くなっていく様子を想像してみましょう。 - \(X\) が小さくなるにつれて、新しく見えるようになる山はあっても、一度見えた山が隠れることはありません。 - 山が新しく見えるようになったとき、その両隣の山が既に見えていれば、それらは1つの「山脈」として繋がります。

このように「要素が追加され、隣接するグループが統合される」という性質は、Union-Find データ構造で効率的に管理できます。

3. オフラインクエリ

クエリをそのままの順番で解くのではなく、雲の高さ \(X_j\) が高い順に並び替えて処理します。これにより、標高の高い山から順に「有効化」していくだけで、すべてのクエリを一度の走査で処理できるようになります。

アルゴリズム

1. 準備:
   • 山の情報を標高 \(A_i\) の降順にソートします。
   • クエリを雲の高さ \(X_j\) の降順にソートします（元の順番を保持しておく必要があります）。
   • 各グループ（山脈）の最大美しさを保持できる Union-Find を用意します。
2. クエリの処理:
   • 各クエリ \(X_j\) について、まだ有効化されていない山のうち \(A_i \geq X_j\) を満たすものをすべて有効化します。
   • 山の有効化手順:
     1. その山 \(i\) を「有効」とし、暫定の眺望値の総和に \(B_i\) を加算します。
     2. 左隣の山 \(i-1\) が有効なら、Union-Find で統合します。このとき、統合前のそれぞれのグループの最大美しさを総和から引き、統合後の新しいグループの最大美しさ（2つのグループの最大値のうち大きい方）を総和に加算します。
     3. 右隣の山 \(i+1\) についても同様に統合処理を行います。
3. 回答の出力:
   • 全クエリ処理後、元のクエリの順番に結果を出力します。

計算量

• 時間計算量: \(O(N \log N + Q \log Q)\)
  • 山とクエリのソートに \(O(N \log N + Q \log Q)\) かかります。
  • Union-Find の操作はほぼ定数時間 \(O(\alpha(N))\) であり、各山を1回ずつ有効化するため、全体で \(O((N+Q) \alpha(N))\) です。
• 空間計算量: \(O(N + Q)\)
  • 山、クエリ、Union-Find の配列などを保持するために必要です。

実装のポイント

• Union-Find の拡張: 通常の Union-Find はグループの連結のみを管理しますが、今回は各ルートノードにそのグループ内の「美しさの最大値 \(B_i\)」を保持させるようにします。

• 総和の更新: 新しく山を追加したりグループを結合したりするたびに、全体の「眺望値の総和」を差分更新することで、各クエリに対して \(O(1)\) で答えを求めることができます。

  ソースコード

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

この解説は gemini-3-flash-thinking によって生成されました。