【精進1】ABC287-G

黄色以上の問題を【精進】として解いていく。現在解いてない黄色の問題はProblemsによると$367$問残っているようなので1日1問程度解けば年内に黄色を埋められる計算になりそれを目指して進めていく

問題

G - Balance Update Query
$N$種類のカードがあり、得点$a_i$と使用可能枚数$b_i$が定まっている。$3$種類のクエリを処理する

• $x$種類目の得点を更新
• $x$種類目の使用可能枚数を更新
• 使用可能枚数を守って$x$枚選ぶときの得点の和の最大を出力

解法

得点順にソートすればセグメント木の2分探索でクエリ$3$が処理できる。事前にどのような得点があり得るのかを知っておく必要があるためクエリを先読みし座圧しておく。まじめにやると$\log$ $2$つから$1$つにできるということだけど、ここらへんのアルゴリズムはよく知らない。atcoder::fenwick_treeではその機能は提供されていないけど、セグメント木である必要があるんだっけ？

コード

#include "/home/y_midori/cp/library/template.hpp"
#include "data_structure/compress.hpp"
#include <atcoder/fenwicktree>
void solve() {
    LL(n);
    vl a(n), b(n);
    Compress<ll> cp;
    rep(i, n) {
        input(a[i], b[i]);
        cp.add(-a[i]);
    }
    cp.add(-inf);
    LL(q);
    vl flag(q), x(q), y(q);
    rep(i, q) {
        input(flag[i]);
        if(flag[i] == 1) {
            input(x[i], y[i]);
            x[i]--;
            cp.add(-y[i]);
        } else if(flag[i] == 2) {
            input(x[i], y[i]);
            x[i]--;
        } else {
            input(x[i]);
        }
    }
    cp.build();
    ll m = cp.size();
    atcoder::fenwick_tree<ll> sz(m + 1), sum(m + 1);
    rep(i, n) {
        sz.add(cp.get(-a[i]), b[i]);
        sum.add(cp.get(-a[i]), a[i] * b[i]);
    }
    rep(i, q) {
        if(flag[i] == 1) {
            sz.add(cp.get(-a[x[i]]), -b[x[i]]);
            sum.add(cp.get(-a[x[i]]), -a[x[i]] * b[x[i]]);
            a[x[i]] = y[i];
            sz.add(cp.get(-a[x[i]]), b[x[i]]);
            sum.add(cp.get(-a[x[i]]), a[x[i]] * b[x[i]]);
        } else if(flag[i] == 2) {
            sz.add(cp.get(-a[x[i]]), y[i] - b[x[i]]);
            sum.add(cp.get(-a[x[i]]), a[x[i]] * (y[i] - b[x[i]]));
            b[x[i]] = y[i];
        } else {
            if(sz.sum(0, m) < x[i]) {
                print(-1);
                continue;
            }
            ll ok = 0, ng = m;
            while(ng > ok + 1) {
                ll mid = (ok + ng) / 2;
                if(sz.sum(0, mid) > x[i]) {
                    ng = mid;
                } else {
                    ok = mid;
                }
            }
            ll ans = sum.sum(0, ok) - cp[ok] * (x[i] - sz.sum(0, ok));
            print(ans);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << std::setprecision(16);
    int t = 1;
    rep(_, t) {
        solve();
    }
}

別解

オンラインで解く方法がここで解説されてる。ポインタ木周りの知識が足りてないので勉強する。