ABC 287 G — Balance Update Query

考察

最大score和を得るには、quotaの範囲でscoreが高いcardから順にx枚選べばよい。

score更新で将来現れる値は全queryを先読みすれば有限集合として得られ、座標圧縮できる。

各score帯についてcard枚数とscore×枚数の両方を持てば、上位帯を丸ごと選んだ価値と閾値帯の一部選択を計算できる。

採用する候補: 全scoreを座標圧縮し、quota総数とscore総和の2本のFenwick treeで更新・上位x枚queryを処理する。

棄却する候補: query 3ごとに全種類をscore順にsortしてquotaを消費する。

最大2×10^5回のqueryで毎回N種類をsortすると間に合わない。

棄却する候補: max heapへcardをquota枚ずつ投入して更新する。

総quotaが大きく、scoreやquotaの変更で古い要素の削除・大量挿入も必要になる。

初期scoreと全type-1更新値を圧縮し、Fenwick Xへ各座標のquota、Yへscore×quotaを入れる。score変更では旧座標からb_iを引き新座標へ足し、quota変更では差分を現在score座標へ反映する。type-3ではX全体がx未満なら-1。そうでなければFenwickのprefix lower_bound等で上位x枚の境界座標を求め、高score側のY合計と境界scoreで残りを計算する。

典型の発動条件

offline座標圧縮

発動条件: 更新値を含む大きなkey集合がquery先読みで既知になるとき。

初期値と全score更新値だけを昇順indexへ写す。

個数・重み和の二重Fenwick

発動条件: 上位k個の値の総和を動的multisetで求めたいとき。

frequencyで順位境界を探し、weighted sumで完全に取る範囲の価値を得る。

閾値bucketの部分採用

発動条件: 同値要素をまとめた順位queryで必要数がbucket途中に達するとき。

境界より上を全採用し、残数だけ同scoreから取る。

問題固有の要素

各kindに10^100枚あってもquotaだけが選択可能数を決めるため、実体cardを生成せずscore別の有限なmultiplicityとして扱える。

別の問題へ持ち帰る視点: 巨大または暗黙の要素集合でも、同値な要素をweight付きbucketへ集約できればorder statisticを処理できる。

正当性

同じscoreのcardは区別不要なので、kind単位ではなくscore座標ごとのquota合計へ集約できる。 上位からcountがxを超える最初のscoreを境界とし、それより高い全cardのweighted sumに、残数×境界scoreを足せばよい。 種類ごとのscore/quota変更を点更新へ変え、順位境界と価値和を対数的に取得できる。

実装上の注意

  • score変更時は現在quota b_iを、quota変更時は現在score a_iを使い、両arrayをquery後に更新する。
  • countとscore総和は64bit整数で持ち、score 0のbucketも圧縮対象から落とさない。
  • Fenwickがprefix方向なら、全体−prefixでsuffix量へ変換するindex境界を揃える。

復習の核

  • 同じscoreの複数kind、score 0、境界bucketを一部だけ使うqueryを作り、Xの枚数差分とYの価値差分が常に同期するか確認する。

計算量と制約

時間

O((N+Q)log(N+Q))、score圧縮とBIT木上順位探索。

空間

O(N+Q)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N,Q \leq 2 \times 10^5; 0 \leq a_i \leq 10^9; 0 \leq b_i \leq 10^4; For each query of the 1-st kind, 1 \leq x \leq N and 0 \leq y \leq 10^9.; For each query of the 2-nd kind, 1 \leq x \leq N and 0 \leq y \leq 10^4.; For each query of the 3-rd kind, 1 \leq x \leq 10^9.; There is at least one query of the 3-rd kind.; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Balance Update Query の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 反転数・重み付き接頭辞統計をFenwick Treeで保つ

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: Fenwick Tree・反転数・重み付き接頭辞統計

    補助タグ: 座標・値の順序保存圧縮

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 反転数・重み付き接頭辞統計をFenwick Treeで保つ

    • 処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。

    先に読む単元:

    この解説で扱わないこと:

    • 一般のモノイドによるSegment Treeの区間要約。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題