概要

雲の高さ \(X\) が与えられたとき、標高 \(X\) 以上の山が形成する連続区間（山脈）ごとに美しさの最大値を求め、その総和を計算する問題です。オフライン処理と Union-Find を用いて効率的に解きます。

考察

素朴なアプローチの問題点

各クエリごとに見える山を列挙し、連続区間に分割して最大値を求めると、1 クエリあたり \(O(N)\) かかり、全体で \(O(NQ)\) となって制約上 TLE になります。

重要な気づき

クエリをオフラインで処理することを考えます。雲の高さ \(X\) を大きい方から小さい方へ処理すると、\(X\) が下がるにつれて見える山が増えていく（一度見えた山は消えない）という単調性があります。

新しい山 \(i\) が見えるようになったとき： - 山 \(i\) は単独で新しい山脈を作り、眺望値 \(B_i\) が総和に加算されます。 - もし隣の山（\(i-1\) や \(i+1\)）がすでに見えていれば、山脈同士が合体します。

山脈の合体時の眺望値変化

2つの山脈が合体する場合を考えます。合体前のそれぞれの眺望値が \(m_1, m_2\) だとすると、合体前の総和への寄与は \(m_1 + m_2\)、合体後は \(\max(m_1, m_2)\) です。したがって総和の減少量は：

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

アルゴリズム

1. 山を標高の降順にソートし、クエリも \(X\) の降順にソートする。
2. Union-Find（DSU）を用意し、各連結成分の美しさの最大値 max_beauty を管理する。
3. クエリを大きい \(X\) から順に処理する。各クエリの前に、標高が \(X\) 以上の山を順次追加する：
   • 山 \(i\) を追加するとき、total += B[i]
   • 左隣 \(i-1\) がすでに見えているなら合体し、total -= min(max_beauty[root_i], max_beauty[root_{i-1}])
   • 右隣 \(i+1\) がすでに見えているなら同様に合体
4. 各クエリの答えはそのときの total の値。

具体例

山が \((A, B) = (5, 10), (3, 20), (4, 5), (6, 8)\) で \(X = 4\) の場合： - 標高 4 以上の山：山1(標高5)、山3(標高4)、山4(標高6) - 見える山の番号：{1, 3, 4} → 山脈 {1} と {3, 4} - 眺望値の総和：\(B_1 + \max(B_3, B_4) = 10 + 8 = 18\)

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • ソートに \(O(N \log N + Q \log Q)\)
  • Union-Find の各操作はほぼ \(O(1)\)（経路圧縮あり）
  • 全体の merge 回数は最大 \(2N\) 回
• 空間計算量: \(O(N + Q)\)

実装のポイント

• オフライン処理：クエリの順番を変えて処理するため、元のインデックスを保持して最後に並べ替えて出力する。

• Union-Find の merge 関数の戻り値：合体による総和の減少量 \(\min(m_1, m_2)\) を返すようにすると、total の更新が簡潔に書ける。

• visible 配列：山がすでに追加済みかどうかを管理し、隣接する山との合体判定に使う。

• ポインタ（ptr）の活用：山を標高降順に並べておき、ポインタを進めることで各クエリに対して必要な山だけを追加する（尺取り法的な発想）。

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。