Overview

This problem asks for the minimum shipping cost when packing “defective products” (those with quality scores below the threshold \(K\)) into boxes by contiguous intervals and shipping them. Since the shipping cost of each box is determined by the maximum weight within it, “grouping each maximal contiguous interval of defective products into a single box” is optimal. Since \(K\) differs for each query, we need to efficiently manage the merging of intervals.

Analysis

1. Strategy to Minimize Shipping Cost

Consider a contiguous interval of defective products. If we split this interval into multiple boxes, the shipping cost becomes the sum of the maximum weights in each box. However, if we group them all into a single box without splitting, the shipping cost is just the single maximum weight of the entire interval. Since the weights \(B_i\) are always positive, “if defective products are contiguous, put them all in one box” is the best strategy to minimize the total shipping cost.

Therefore, the problem can be rephrased as “find the sum of maximum weights over each contiguous interval formed by products satisfying quality score \(A_i < K\).”

2. Efficient Processing of Queries

If we compute independently for each query \(K_j\), it takes \(O(N)\) per query, resulting in \(O(NQ)\) overall, which is too slow (\(N, Q \leq 2 \times 10^5\)). Here, we note the property that as the threshold \(K\) increases, the number of defective products increases, and “once a product becomes defective, it remains defective for all larger values of \(K\).”

By sorting and processing queries \(K_j\) in ascending order, we can dynamically update the shipping cost while transitioning products from “non-defective” to “defective” in a one-way manner.

Algorithm

The process of merging adjacent defective products as they transition from “non-defective” to “defective” can be efficiently performed using Union-Find (DSU: Disjoint Set Union).

1. Preprocessing:

   • Sort products in ascending order of quality score \(A_i\).
   • Sort queries in ascending order of threshold \(K_j\) (remembering the original order).
   • Prepare a DSU, with each element initially holding the weight \(B_i\) of that product.

2. Processing Queries:

   • For the current \(K_j\), sequentially “activate” products that newly become defective (\(A_i < K_j\)).
   • When product \(i\) is activated:
     • First, add its individual shipping cost \(B_i\) to the total.
     • If a neighbor (\(i-1\) or \(i+1\)) is already defective, merge them using DSU.
     • When merging, update the shipping cost difference by adding ”(maximum weight after merging) - (sum of maximum weights of each group before merging)” to the total.

3. Output Results:

   • After processing all queries, output results in the original query order.

Complexity

• Time Complexity: \(O((N + Q) \log (N + Q))\)
  • Sorting products and queries takes \(O(N \log N + Q \log Q)\).
  • DSU operations are nearly constant time (inverse Ackermann function \(\alpha(N)\)), and activation and merging of each product happens at most a few times, so it is \(O(N \alpha(N))\).
• Space Complexity: \(O(N + Q)\)
  • Required to store product data, query data, and DSU arrays.

Implementation Notes

• Extended DSU: In addition to the standard DSU (parent management), maintain the maximum weight max_b within each group.

• Shipping Cost Update Formula: When merging two groups \(u, v\), the change in total shipping cost is max(max_b[u], max_b[v]) - (max_b[u] + max_b[v]).

• Boundary Conditions: When processing products at the edges (the \(1\)st or \(N\)th product), be careful to check whether a neighbor exists.

  Source Code

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

This editorial was generated by gemini-3-flash-thinking.