\(Q\) 個のクエリについて、\(A_i<K\) を満たす \(i\) についての連続する区間のうちの \(B_i\) の最大値の合計を求める問題です。

\(K\) を昇順にみていって、\(A_i<K\) を満たす \(i\) を更新しながらクエリに答えていくことを考えます。これは満たす \(i\) は減ることがなく増えるだけで、増える回数が高々 \(N\) 回と少ないからです。

連続した区間を管理するテクニックとしてsetで区間を管理する方法やUnion Findを用いる方法があります。

今回はUnion Findを用いる方法を解説します。

\(A_i<K\) を満たす \(i\) がなす区間の更新を考えます。 新たに \(i\) 番目の製品が不良品として増えたとします。この時、\(i-1\) 番目、\(i+1\) 番目の製品がそれぞれ不良品だった場合にそれらの区間とマージするというような処理を考えます。

不良品の区間をマージする時はその最大値を引いて、マージ後の区間の最大値を加えると常に今ある区間についての総和が求められます。

クエリのソートと、製品のソートがボトルネックとなり、時間計算量 \(\mathrm{O}((N+Q)\log(N+Q))\) などになります。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
    vector<int> k(q);
    for (auto& e : k) cin >> e;
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return k[i] < k[j]; });
    vector<int> orda(n);
    iota(orda.begin(), orda.end(), 0);
    sort(orda.begin(), orda.end(), [&](int i, int j) { return a[i] < a[j]; });
    atcoder::dsu uf(n);
    int idx = 0;
    long long ans = 0;
    vector<int> vis(n);
    vector<long long> res(q);
    for (auto i : ord) {
        while (idx < n && a[orda[idx]] < k[i]) {
            const int id = orda[idx];
            if (id > 0 && vis[id - 1]) {
                int prevr = uf.leader(id - 1);
                ans -= b[prevr];
                int prevr2 = uf.leader(id);
                int nv = uf.merge(id - 1, id);
                b[nv] = max(b[prevr], b[prevr2]);
            }
            if (id + 1 < n && vis[id + 1]) {
                int prevr = uf.leader(id + 1);
                ans -= b[prevr];
                int prevr2 = uf.leader(id);
                int nv = uf.merge(id, id + 1);
                b[nv] = max(b[prevr], b[prevr2]);
            }
            ans += b[uf.leader(id)];
            vis[id] = 1;
            idx++;
        }
        res[i] = ans;
    }
    for (auto& e : res) cout << e << endl;
}