概要

基準値 \(K\) に対して、\(A_i < K\) となる製品を「不良品」とし、連続する不良品の区間ごとに重さ \(B_i\) の最大値を足した値を求める問題です。

各問い合わせを独立に処理すると重いので、\(K\) の昇順に処理しながら、不良品になる製品を少しずつ追加していきます。

考察

まず、ある基準値 \(K\) が固定されているとします。

不良品は \(A_i < K\) の製品です。箱には、元の並びで連続する不良品しか入れられません。

例えば、不良品が次のように並んでいたとします。

不良 不良 良品 不良 不良 不良 良品 不良

このとき、不良品の連続区間は次の \(3\) つです。

[不良 不良], [不良 不良 不良], [不良]

同じ連続区間内の不良品は、まとめて \(1\) つの箱に入れるのが最適です。

理由は、箱の送料が「その箱に入っている \(B_i\) の最大値」だからです。

ある連続区間の最大重量を \(M\) とすると、その区間全体を \(1\) 箱に入れれば送料は \(M\) です。

もし区間を複数の箱に分けると、最大重量 \(M\) を含む箱の送料だけで少なくとも \(M\) かかり、さらに他の箱の送料も正の値なので、合計は \(M\) 以上になります。

したがって、最小送料は

不良品の各連続区間について、その区間内の \(B_i\) の最大値を足し合わせたもの

になります。

---

素朴に各問い合わせごとに全製品を走査すると、計算量は \(O(NQ)\) です。

制約では \(N + Q \leq 2 \times 10^5\) なので、最悪で \(O(10^{10})\) 程度になり、間に合いません。

そこで、問い合わせを \(K\) の昇順に処理します。

\(K\) が大きくなるほど、条件 \(A_i < K\) を満たす製品は増えるだけで、減ることはありません。

つまり、不良品の集合は単調に増加します。

この性質を利用して、製品を \(A_i\) の昇順に見ていき、各問い合わせで新たに不良品になる製品だけを追加します。

不良品の連続区間は、Union-Find で管理できます。

新しく位置 \(i\) の製品が不良品になったとき、

• まず単独の区間として追加する
• 左隣 \(i-1\) がすでに不良品なら結合する
• 右隣 \(i+1\) がすでに不良品なら結合する

という処理をします。

各連続区間について、その区間内の \(B_i\) の最大値を持っておけば、答えの合計も更新できます。

アルゴリズム

各連続区間を Union-Find の連結成分として扱います。

各連結成分について、次の情報を持ちます。

• 親 parent
• サイズ sz
• その区間内の \(B_i\) の最大値 compMax

また、現在の答えを cur として持ちます。

cur は、現在不良品になっている各連続区間の compMax の合計です。

---

処理手順は以下の通りです。

1. 製品を \((A_i, i)\) の形で保存し、\(A_i\) の昇順にソートする
2. 問い合わせを \((K_j, j)\) の形で保存し、\(K_j\) の昇順にソートする
3. まだ不良品として追加していない製品を指すポインタ ptr を用意する
4. 各問い合わせ \(K\) を昇順に処理する
   • \(A_i < K\) を満たす製品を順に追加する
   • 位置 pos を不良品として有効化する
   • cur += B[pos] として、単独区間を追加する
   • 左隣が有効なら Union-Find で結合する
   • 右隣が有効なら Union-Find で結合する
   • 結合時には、古い区間の最大値を cur から引き、新しい区間の最大値を足す
5. その時点の cur が、その問い合わせの答えになる
6. 問い合わせはソートして処理しているので、元の順番に戻して出力する

---

結合時の更新は次のようになります。

2つの区間の最大値をそれぞれ \(x, y\) とすると、結合前の答えには \(x + y\) が含まれています。

結合後は1つの区間になり、その最大値は \(\max(x, y)\) です。

したがって、

\[ cur \leftarrow cur - x - y + \max(x, y) \]

と更新します。

コードではこれを unite 関数の中で行っています。

計算量

• 時間計算量: \(O((N + Q)\log(N + Q))\)
• 空間計算量: \(O(N + Q)\)

製品と問い合わせのソートに \(O(N\log N + Q\log Q)\) かかります。

Union-Find の操作はほぼ定数時間で、全体で \(O(N \alpha(N))\) 程度です。ここで \(\alpha(N)\) はアッカーマン関数の逆関数で、実用上は定数とみなせます。

実装のポイント

• 条件は \(A_i < K\) なので、追加処理の条件も A < K にする必要があります。

• 問い合わせは昇順に並べ替えて処理するため、元のインデックスを一緒に保存しておきます。

• 位置 pos の左右がすでに不良品かどうかを判定するために、active[pos] を用意します。

• 答えは最大で \(N \times 10^9\) 程度になる可能性があるため、long long を使います。

  ソースコード

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

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

    int N, Q;
    cin >> N >> Q;

    vector<long long> B(N);
    vector<tuple<long long, int>> items;
    items.reserve(N);

    for (int i = 0; i < N; i++) {
        long long A;
        cin >> A >> B[i];
        items.emplace_back(A, i);
    }

    vector<pair<long long, int>> queries(Q);
    for (int i = 0; i < Q; i++) {
        long long K;
        cin >> K;
        queries[i] = {K, i};
    }

    sort(items.begin(), items.end());
    sort(queries.begin(), queries.end());

    vector<int> parent(N), sz(N, 1);
    vector<long long> compMax(N, 0);
    vector<char> active(N, 0);

    iota(parent.begin(), parent.end(), 0);

    auto find_root = [&](auto&& self, int x) -> int {
        if (parent[x] == x) return x;
        return parent[x] = self(self, parent[x]);
    };

    long long cur = 0;

    auto unite = [&](int x, int y) {
        int rx = find_root(find_root, x);
        int ry = find_root(find_root, y);
        if (rx == ry) return;

        cur -= compMax[rx];
        cur -= compMax[ry];

        if (sz[rx] < sz[ry]) swap(rx, ry);
        parent[ry] = rx;
        sz[rx] += sz[ry];
        compMax[rx] = max(compMax[rx], compMax[ry]);

        cur += compMax[rx];
    };

    vector<long long> ans(Q);
    int ptr = 0;

    for (auto [K, qi] : queries) {
        while (ptr < N && get<0>(items[ptr]) < K) {
            int pos = get<1>(items[ptr]);
            active[pos] = 1;
            parent[pos] = pos;
            sz[pos] = 1;
            compMax[pos] = B[pos];
            cur += B[pos];

            if (pos > 0 && active[pos - 1]) unite(pos, pos - 1);
            if (pos + 1 < N && active[pos + 1]) unite(pos, pos + 1);

            ptr++;
        }
        ans[qi] = cur;
    }

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

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。