かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC287 G - Balance Update Query

データ構造競技プログラミング解説 ABC

問題はこちら

目次

問題概要
解説
提出プログラム
感想

問題概要

${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}$ として左の子に遷移して再帰的に求めていけばよいです．

2番目のクエリや4番目のクエリのような更新では，更新前の得点や枚数を各ノードから引き，更新後の得点や枚数を足していけばよいです．

提出プログラム

https://atcoder.jp/contests/abc287/submissions/38668500

感想