ABC 368 G — Add and Multiply Queries

考察

位置iでの最適更新はv=max(v+A_i,v·B_i)である。B_i=1なら必ず加算なので、判断が必要なのはB_i>1の位置だけである。

v>0になった後、B_i>1の位置では乗算を選べば少なくとも2倍、加算を選ぶ場合もA_i>v(B_i−1)≥vなので結果は2倍超になる。答え上限から判断回数は少ない。

採用する候補: Aのrange sumとB>1のindex集合を動的管理し、queryでは特殊index間を一括加算して各特殊点だけ比較する。

長いB=1区間をまとめ、値が倍増する特殊点は一queryでごく少数しか訪れない。

棄却する候補: type 3ごとにl..rの全位置でmax(v+A_i,vB_i)を計算する。

式自体は正しいが、長いrange queryが多数ある場合に更新の局所性を活かせない。

AはFenwick treeまたはsegment treeで区間和を持ち、B_i>1のindexはordered setで次位置をlower_bound取得する。

開始v=0では乗算が0なので最初の要素は加算する。以後、処理する特殊indexごとにvが倍増し10^18保証がiteration上限を与える。

type 1ではAのrange-sum構造を一点更新し、type 2ではB_i>1かに応じてordered setを挿入・削除する。type 3ではpos=lから次の特殊index jまでのA和をvへ足し、j≤rならv=max(v+A_j,vB_j)として先へ進む。残りA和を加えて出力する。

典型の発動条件

例外位置だけの区間simulation

発動条件: 大多数の位置が加法などまとめられる遷移で、少数位置だけ個別判断が要るとき。

例外indexをordered setで列挙し、通常区間をrange aggregateする。

値倍増による反復回数上界

発動条件: 訪れる例外ごとに値が一定倍率以上増え、答えに上限があるとき。

例外数自体が多くても一queryで実処理する数を数値上限で抑える。

問題固有の要素

「乗算を選ばなかった」特殊点でも、選ばない条件がA_i>v(B_i−1)を意味して加算後に倍増する。

別の問題へ持ち帰る視点: 分岐algorithmのiteration boundは、どちらのbranchでも同じprogress measureが増えるか確認する。

正当性

各位置の二候補v+A_iとvB_iはvについて非減少なので、現在の最大値を残すと、任意の後続操作列に対して小さい現在値を残すより不利にならない。従ってv=max(v+A_i,vB_i)を各位置で行うgreedyが全区間の最大値を与える。B_i=1では加算が最大であり、その連続区間をAの区間和でまとめても同じ値になる。B_i>1の位置だけ個別に処理すれば全候補操作を網羅する。A_i≥1なので最初の加算でv>0となり、その後の特殊位置では最大候補が少なくとも2v、最終値≤10^18という保証から特殊位置の処理総数はO(log 10^18)。この上界と区間和・次の特殊indexの検索により高速化を正当化できる。

実装上の注意

  • 特殊index jのA_jを手前の区間和へ重複させず、[pos,j)とjを分ける。B更新で1との境界を正しくsetへ反映する。

復習の核

  • B=1のみ、l=r、特殊点が連続する例で区間境界を追う。倍増証明はvが正になる最初の加算後から適用する。

計算量と制約

時間

各照会O(log N·log V)、V≤10¹⁸は照会途中値上限。更新O(log N)。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^5; 1 \leq A_i \leq 10^9; 1 \leq B_i \leq 10^9; 1 \leq Q \leq 10^5; For type 1 and 2 queries, 1 \leq i \leq N.; For type 1 and 2 queries, 1 \leq x \leq 10^9.; For type 3 queries, 1 \leq l \leq r \leq N.; For type 3 queries, the value to be printed is at most 10^{18}.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Add and Multiply Queries の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 単調進行による償却解析

主題
  • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 単調進行による償却解析

    補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計 ordered set・multisetの動的順序管理

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

    学習の位置

    体系上の位置: 単調進行による償却解析

    • 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題