概要

\(N\) 個の製品を基準値 \(K\) で不良品に分類し、連続する不良品ブロックごとに「重量の最大値」を送料として支払うとき、送料合計の最小値を \(Q\) 個のクエリそれぞれについて求める問題です。

考察

1つの連続ブロックの最適な箱詰め

連続する不良品のブロック \([l, r]\) を複数の箱に分けると、各箱の送料（=箱内の重量の最大値）の合計は、ブロック全体を1箱にまとめたときの送料（=ブロック全体の重量の最大値）以上になります。

例えば重量が \([3, 5, 2]\) のブロックを \([3,5]\) と \([2]\) に分けると送料は \(5+2=7\) ですが、まとめれば \(5\) です。

したがって、各連続不良品ブロックは1箱にまとめるのが最適です。答えは「各最大連続不良品ブロックの重量最大値の総和」となります。

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

各クエリごとに不良品を判定しブロックの最大値を求めると、1クエリあたり \(O(N)\) で全体 \(O(NQ)\) となり、\(N+Q \leq 2 \times 10^5\) の制約下で最悪 \(O(10^{10})\) 近くなりTLEします。

クエリをソートしてオフライン処理

基準値 \(K\) を小さい順に処理すると、\(K\) が増えるにつれて不良品が増えていく（品質スコアが小さい製品から順に不良品になる）ことに着目します。新しく不良品になった製品を1つずつ追加し、隣接する既存の不良品ブロックとのマージを管理すれば効率的に答えを更新できます。

アルゴリズム

1. 製品を品質スコア \(A_i\) の昇順にソートする。
2. クエリを \(K_j\) の昇順にソートする。
3. Union-Find（DSU） を用意し、各連合（ブロック）の重量最大値 mx を管理する。変数 total で送料合計を保持する。
4. クエリ \(K_j\) を順に処理する。\(A_i < K_j\) を満たす未処理の製品を品質スコアが小さい順に追加する：
   • 製品 \(i\) を追加：total += B[i]（新しい1要素ブロック、送料 \(B_i\)）
   • 左隣 \(i-1\) が既に不良品なら、ブロックをマージする。マージ前の2ブロックの送料合計は \(\text{mx}[a] + \text{mx}[b]\)、マージ後は \(\max(\text{mx}[a], \text{mx}[b])\)。差分だけ total を減らす。
   • 右隣 \(i+1\) についても同様にマージする。
5. 追加完了後の total がそのクエリの答え。

具体例: 製品の重量が \(B = [3, 5, 2]\) で全て不良品の場合： - 製品0追加：total = 3 - 製品1追加：total = 3+5 = 8 → 左とマージ、削減 \(= 3+5-5=3\) → total = 5 - 製品2追加：total = 5+2 = 7 → 左とマージ、削減 \(= 5+2-5=2\) → total = 5

最終結果 \(5 = \max(3,5,2)\)。正しいです。

計算量

• 時間計算量: \(O((N + Q) \log(N + Q))\)
  • 製品のソート \(O(N \log N)\)、クエリのソート \(O(Q \log Q)\)、Union-Find の操作は全体で \(O(N \cdot \alpha(N))\)（ほぼ線形）
• 空間計算量: \(O(N + Q)\)

実装のポイント

• Union-Find の unite 関数が「コスト削減量」を返す設計が鍵。マージ前の2ブロックの最大値の和から、マージ後の最大値を引いた値を返すことで、total の更新が簡潔になります。

• active 配列で各製品が既に不良品として追加済みかを管理し、隣接マージの判定に使います。

• クエリはオフライン処理（ソートして一括処理）するため、元のクエリ順序を queries[j].second に保存し、最後に元の順序で出力します。

• dsu.mx[i] の初期化は製品追加時に行い、追加前は \(0\) のままにしておく点に注意が必要です。

  ソースコード

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

struct DSU {
    vector<int> parent, rnk;
    vector<long long> mx;
    DSU(int n) : parent(n), rnk(n, 0), mx(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    }
    long long unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return 0;
        long long old_sum = mx[a] + mx[b];
        long long new_max = max(mx[a], mx[b]);
        if (rnk[a] < rnk[b]) swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
        mx[a] = new_max;
        return old_sum - new_max;
    }
};

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

    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<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){ return A[a] < A[b]; });

    vector<pair<int,int>> queries(Q);
    for(int j = 0; j < Q; j++){
        cin >> queries[j].first;
        queries[j].second = j;
    }
    sort(queries.begin(), queries.end());

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

    int ptr = 0;
    for(int j = 0; j < Q; j++){
        int K = queries[j].first;
        while(ptr < N && A[order[ptr]] < K){
            int i = order[ptr];
            active[i] = true;
            dsu.mx[i] = B[i];
            total += B[i];
            if(i > 0 && active[i-1]){
                total -= dsu.unite(i, i-1);
            }
            if(i < N-1 && active[i+1]){
                total -= dsu.unite(i, i+1);
            }
            ptr++;
        }
        ans[queries[j].second] = total;
    }

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

---

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