概要

品質スコアが基準値 \(K\) 未満の「不良品」を、連続する区間ごとに箱詰めして発送する際の最小送料を求める問題です。 各箱の送料はその中の最大重量で決まるため、「不良品の極大な連続区間をそれぞれ一つの箱にまとめる」のが最適となります。クエリごとに \(K\) が異なるため、効率的に区間の結合を管理する必要があります。

考察

1. 送料を最小化する戦略

ある連続した不良品の区間を考えます。この区間を複数の箱に分割すると、それぞれの箱の最大重量の和が送料になります。しかし、分割せずに一つの箱にまとめると、送料はその区間全体の最大重量一つ分だけで済みます。 重量 \(B_i\) は常に正であるため、「不良品が連続しているなら、それらをすべて一つの箱に入れる」ことが、送料の合計を最小化する最善の戦略です。

したがって、問題は「品質スコア \(A_i < K\) を満たす製品たちが作る、各連続区間の最大重量の総和を求める」ことと言い換えられます。

2. クエリの効率的な処理

各クエリ \(K_j\) に対して独立に計算すると、1回あたり \(O(N)\) かかり、全体で \(O(NQ)\) となって間に合いません（\(N, Q \leq 2 \times 10^5\)）。 ここで、基準値 \(K\) が大きくなるほど不良品の種類が増え、「一度不良品になった製品は、より大きな \(K\) に対しても不良品であり続ける」という性質に注目します。

クエリ \(K_j\) を昇順（小さい順）に並べ替えて処理することで、製品を「良品」から「不良品」へと一本道で変化させながら、動的に送料を更新していくことができます。

アルゴリズム

「良品」から「不良品」へ変化する過程で、隣り合う不良品同士を結合していく操作は、Union-Find (DSU: Disjoint Set Union) を用いて効率的に行えます。

1. 事前準備:

   • 製品を品質スコア \(A_i\) の昇順にソートします。
   • クエリを基準値 \(K_j\) の昇順にソートします（元の順番を覚えておきます）。
   • DSUを用意し、各要素の初期状態としてその製品の重量 \(B_i\) を保持させます。

2. クエリの処理:

   • 現在の \(K_j\) に対して、新しく不良品になる製品（\(A_i < K_j\)）を順番に「有効化」します。
   • 製品 \(i\) が有効化されたら：
     • まず、その製品単独の送料 \(B_i\) を合計に加算します。
     • 隣（\(i-1\) や \(i+1\)）がすでに不良品であれば、DSUでそれらを統合します。
     • 統合する際、「(統合後の最大重量) - (統合前の各グループの最大重量の和)」 を合計に加算することで、送料の差分を更新します。

3. 回答の出力:

   • 全てのクエリを処理した後、元のクエリの順番で結果を出力します。

計算量

• 時間計算量: \(O((N + Q) \log (N + Q))\)
  • 製品とクエリのソートに \(O(N \log N + Q \log Q)\) かかります。
  • DSUの操作はほぼ定数時間（アッカーマン関数の逆関数 \(\alpha(N)\)）であり、各製品の有効化と結合は高々数回なので \(O(N \alpha(N))\) です。
• 空間計算量: \(O(N + Q)\)
  • 製品データ、クエリデータ、DSUの配列を保持するために必要です。

実装のポイント

• DSUの拡張: 通常のDSU（親の管理）に加えて、各グループ内の重量の最大値 max_b を保持するようにします。

• 送料の更新式: 2つのグループ \(u, v\) を統合するとき、全体の送料合計の変化量は max(max_b[u], max_b[v]) - (max_b[u] + max_b[v]) となります。

• 境界条件: 製品の端（\(1\) 番目や \(N\) 番目）を処理する際、隣が存在するかどうかの判定に注意してください。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 問題の要約:
 * 品質スコア A_i < K となる製品が不良品であり、不良品のみからなる連続する区間を箱に詰める。
 * 各箱の送料はその箱に含まれる製品の重量 B_i の最大値である。
 * 全体の送料の合計を最小化したい。
 * 
 * 考察:
 * 不良品からなるある連続した区間を箱に分ける際、送料の合計を最小にするには、
 * その区間全体を1つの箱に入れるのが最適である（分割すると送料の合計は変わらないか増えるため）。
 * したがって、最小の送料合計は、不良品が成す各極大連続区間における B_i の最大値の和となる。
 * 
 * 解法:
 * クエリ K を昇順にソートし、DSU（並列森）を用いて不良品の区間を管理する。
 * K が増加するにつれて不良品が増えていくため、新たに不良品となった製品を
 * その両隣の不良品区間と統合しながら、各区間の最大重量の合計を更新していく。
 */

// 製品情報を格納する構造体
struct Product {
    int a;
    int b;
    int id;
};

// クエリ情報を格納する構造体
struct Query {
    int k;
    int id;
};

// 素集合データ構造 (DSU)
struct DSU {
    vector<int> parent;
    vector<int> rank;
    vector<long long> max_b;

    DSU(int n, const vector<long long>& b) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        max_b.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
            max_b[i] = b[i - 1];
        }
    }

    // 代表元を検索
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    // 2つの集合を統合し、全体の最大値の和の変化量を返す
    long long unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            long long old_max_sum = max_b[root_i] + max_b[root_j];
            if (rank[root_i] < rank[root_j]) {
                parent[root_i] = root_j;
                max_b[root_j] = max(max_b[root_i], max_b[root_j]);
                return max_b[root_j] - old_max_sum;
            } else {
                parent[root_j] = root_i;
                max_b[root_i] = max(max_b[root_i], max_b[root_j]);
                if (rank[root_i] == rank[root_j]) rank[root_i]++;
                return max_b[root_i] - old_max_sum;
            }
        }
        return 0;
    }
};

int main() {
    // 入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    vector<Product> products(N);
    vector<long long> B(N);
    for (int i = 0; i < N; ++i) {
        cin >> products[i].a >> products[i].b;
        products[i].id = i + 1; // 1-indexed
        B[i] = products[i].b;
    }

    vector<Query> queries(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> queries[i].k;
        queries[i].id = i;
    }

    // 製品を品質スコア A_i の昇順にソート
    sort(products.begin(), products.end(), [](const Product& a, const Product& b) {
        if (a.a != b.a) return a.a < b.a;
        return a.id < b.id;
    });

    // クエリを基準値 K の昇順にソート
    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.k < b.k;
    });

    DSU dsu(N, B);
    vector<bool> is_defective(N + 2, false);
    vector<long long> results(Q);
    long long current_total_max_sum = 0;
    int prod_idx = 0;

    // クエリを順番に処理
    for (int i = 0; i < Q; ++i) {
        // 現在の基準値 K 未満の品質スコアを持つ製品を不良品として追加
        while (prod_idx < N && products[prod_idx].a < queries[i].k) {
            int pos = products[prod_idx].id;
            is_defective[pos] = true;
            // 新しい不良品が追加された直後は、その製品のみからなる区間として合計に加算
            current_total_max_sum += B[pos - 1];

            // 左隣が不良品なら区間を統合
            if (pos > 1 && is_defective[pos - 1]) {
                current_total_max_sum += dsu.unite(pos, pos - 1);
            }
            // 右隣が不良品なら区間を統合
            if (pos < N && is_defective[pos + 1]) {
                current_total_max_sum += dsu.unite(pos, pos + 1);
            }
            prod_idx++;
        }
        // 元のクエリのインデックスに結果を格納
        results[queries[i].id] = current_total_max_sum;
    }

    // 結果を出力
    for (int i = 0; i < Q; ++i) {
        cout << results[i] << "\n";
    }

    return 0;
}

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