https://kanpurin.hatenablog.com/entry/2023/02/06/230403

問題はこちら

問題概要

${N}$ 種類のカードがあり，最初， ${i}$ 種類目のカードの得点は ${a_i}$ ，枚数は ${b_i}$ 枚である．以下の形式の ${Q}$ 個のクエリを順に処理せよ．

${x}$ 種類目のカードの得点を ${y}$ に変更
${x}$ 種類目のカードの枚数を ${y}$ に変更
${x}$ 枚のカードを選ぶときの得点の総和の最大値を求める．

${1\leq N,Q\leq 2×10^5}$
${1\leq a_i\leq 10^9}$
${1\leq b_i\leq 10^4}$

解説

各ノードに部分木の得点の総和とカードの枚数の総和を持つBinary Trieを作ると，各クエリ ${O(\log{a_{\max}})}$ で処理することができます．

サンプル1を例に挙げて説明します．

初期状態のBinaryTrieは以下のようになります．

最初のクエリでは， ${x=4}$ 枚使った最大の総得点を求めます．
根の右の子の枚数が ${5}$ であることから左の子のカードを使うことはありません．したがって，右の部分木について答えればよいです．
そのさらに右の子を見ると，枚数が ${3}$ 枚なので右の子のカードはすべて使い， ${x\leftarrow x-3}$ として左の子に遷移して再帰的に求めていけばよいです．