Overview

Given \(N\) products classified as defective based on a threshold \(K\), where shipping cost is paid as the “maximum weight” for each contiguous block of defective products, the problem asks to find the minimum total shipping cost for each of \(Q\) queries.

Analysis

Optimal Packing for a Single Contiguous Block

When a contiguous block of defective products \([l, r]\) is split into multiple boxes, the sum of shipping costs (= maximum weight in each box) is at least the shipping cost of putting the entire block into one box (= maximum weight of the entire block).

For example, if a block has weights \([3, 5, 2]\) and is split into \([3,5]\) and \([2]\), the shipping cost is \(5+2=7\), but combining them gives \(5\).

Therefore, it is optimal to put each contiguous defective block into one box. The answer is “the sum of the maximum weights of each maximal contiguous defective block.”

Issues with the Naive Approach

If we determine defective products and find block maximums for each query, it takes \(O(N)\) per query, giving \(O(NQ)\) overall. Under the constraint \(N+Q \leq 2 \times 10^5\), this approaches \(O(10^{10})\) in the worst case and results in TLE.

Sorting Queries for Offline Processing

We focus on the fact that when processing thresholds \(K\) in increasing order, defective products increase as \(K\) grows (products become defective in order of increasing quality score). By adding newly defective products one at a time and managing merges with adjacent existing defective blocks, we can efficiently update the answer.

Algorithm

1. Sort products in ascending order of quality score \(A_i\).
2. Sort queries in ascending order of \(K_j\).
3. Prepare a Union-Find (DSU) that manages the maximum weight mx of each union (block). Maintain a variable total for the total shipping cost.
4. Process queries \(K_j\) in order. Add unprocessed products satisfying \(A_i < K_j\) in ascending order of quality score:
   • Adding product \(i\): total += B[i] (a new single-element block with shipping cost \(B_i\))
   • If the left neighbor \(i-1\) is already defective, merge the blocks. The sum of shipping costs of the two blocks before merging is \(\text{mx}[a] + \text{mx}[b]\), and after merging it is \(\max(\text{mx}[a], \text{mx}[b])\). Decrease total by the difference.
   • Do the same for the right neighbor \(i+1\).
5. The value of total after all additions is the answer for that query.

Concrete example: If product weights are \(B = [3, 5, 2]\) and all are defective: - Add product 0: total = 3 - Add product 1: total = 3+5 = 8 → merge with left, reduction \(= 3+5-5=3\) → total = 5 - Add product 2: total = 5+2 = 7 → merge with left, reduction \(= 5+2-5=2\) → total = 5

Final result \(5 = \max(3,5,2)\). Correct.

Complexity

• Time complexity: \(O((N + Q) \log(N + Q))\)
  • Sorting products \(O(N \log N)\), sorting queries \(O(Q \log Q)\), Union-Find operations are \(O(N \cdot \alpha(N))\) in total (nearly linear)
• Space complexity: \(O(N + Q)\)

Implementation Notes

• The key design is that the Union-Find’s unite function returns the “cost reduction”. By returning the sum of the maximums of the two blocks before merging minus the maximum after merging, updating total becomes concise.

• An active array manages whether each product has already been added as defective, used for determining adjacent merges.

• Since queries are processed offline (sorted and processed in batch), the original query order is saved in queries[j].second, and results are output in the original order at the end.

• Note that dsu.mx[i] is initialized when a product is added; before addition, it remains \(0\).

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.