考察
一回の区間攻撃の費用は区間内の最大Bで決まる。同じ最大Bを保つ範囲まで広げても、余分に体力を削ることに不利益はない。Bが同じなら右端を代表とする最大Cartesian treeを作ると、各代表の攻撃区間はその部分木区間になる。この区間だけで最適解を表せる。
部分木iが祖先からj回攻撃済みのときの最小追加費用をF_i(j)とする。子の和G(j)=F_left(j)+F_right(j)、欠けた子の関数を0とすると
F_i(j) = min_{k≥max(A_i−j,0)} { k B_i + G(j+k) }
= min_{t≥max(A_i,j)} { t B_i + G(t) } − j B_i
である。葉はF_i(j)=B_i max(A_i−j,0)。子の関数が減少・離散凸なら、限界節約d(j)=G(j)−G(j+1)は非増加。tを一つ増やす費用差はB_i−d(t)なので、A_i以上でd(t)<B_iとなる最初の整数j_0まで進めればよい。同値d(t)=B_iでは費用が変わらないので先へ進む規約とする。このとき
j≤j_0: F_i(j)=G(j_0)+(j_0−j)B_i
j≥j_0: F_i(j)=G(j)
となり、j_0で連続し、切替後の傾き−d(j_0)は−B_iより大きい。従って凸性も帰納できる。
A_i,B_i≤10^9なので、全jを配列に並べたり、B_i個の単位hingeを作ったりはできない。関数をv=F(0)、初期節約d=F(0)−F(1)、重み付きeventのmultisetで表す。event(z,w)はz≥1において節約がwだけ減り、傾きがwだけ増すこと、すなわちw=d(z−1)−d(z)>0を意味する。値は
F(j)=v−d j+Σ_{(z,w)} w max(j−z,0)
で復元できる。葉の表現はv=A_iB_i、d=B_i、event(A_i,B_i)。欠けた子はv=d=0、eventなし。和Gはvとdを足し、二つのevent集合を併合する。同じ座標のeventは別々に残しても、重みを足してもよい。
Gを前からたどってj_0を探す。cur=0、value=G(0)、saving=d(0)で始め、最小event(z,w)について、z≤A_iまたはsaving≥B_iなら、次の二式を行ってeventを取り除く。
value ← value − (z−cur) saving
cur ← z; saving ← saving − w
同じ座標では全eventを処理する。終了後cur<A_iならvalue−=(A_i−cur)saving、cur=A_iとする。この時点でcur=j_0、value=G(j_0)、saving=d(j_0)<B_iである。eventがない場合はsaving=0なので、必要ならA_iまで一度に進めばよい。
親の表現はv=value+j_0B_i、初期節約B_iへ置き換え、event(j_0,B_i−saving)を一つ挿入する。取り除いたのはz≤j_0のevent全てで、それより後はGと同じ。公式入力はA_i≥1なのでj_0≥1であり、座標0のeventは不要。葉からpostorderで処理し、根のvを答える。
例えばG(j)=3max(2−j,0)+4max(5−j,0)ならv=26、saving=7、eventは(2,3),(5,4)。A_i=1,B_i=10では次eventへ進まず、j_0=1、G(1)=19。親はv=29、初期節約10、event(1,3),(2,3),(5,4)となり、F(1)=19、F(2)=12へ接続する。重み3,4を保持することで大きなBでもevent数は増えない。
典型の発動条件
Cartesian tree
発動条件: 各区間の最大値で操作費用が決まり、最大要素を境に左右が独立するとき。
shield B の最大位置を根にし、最大値支配区間の包含関係を二分木へする。
離散凸関数のbreakpoint表現
発動条件: 巨大な整数引数上のDP関数が単調な傾きを持ち、和・prefix切替で更新されるとき。
初期値・傾き・二階差分eventだけを保持してmin-plus recurrenceを評価する。
small-to-large merge
発動条件: 木DPで各部分木のordered event集合を親へ併合し、要素の移動回数を抑えたいとき。
左右の小さい集合を大きい集合へ挿入して折れ線を合成する。
問題固有の要素
最大shieldの区間攻撃を何回まとめて行うかは、子部分木で1回余分に攻撃して節約できる限界費用とB_iの比較で決まる。
別の問題へ持ち帰る視点: 階層的な一括操作では、親操作の単価と子解の限界差分を比較し、最適回数を傾きの閾値として探す。
正当性
同じ最大Bを保つ区間拡張は費用を増やさず、Cartesian treeの部分木攻撃だけに正規化できる。祖先攻撃jの下で根iを倒す条件はk≥max(A_i−j,0)であり、左右は独立だから本文の漸化式が最適追加費用を表す。Gの限界節約dが非増加なのでB_i−d(t)は非減少で、A_i以降の最小値は最初のd(t)<B_iのj_0で得られる。j≥j_0では追加攻撃0が最適、j≤j_0ではj_0まで攻撃する。切替は連続で傾きが増すので減少・凸性を保つ。event間の値更新は一定傾きで進む式そのもので、旧prefixの全eventを消し、重みB_i−d(j_0)を追加すると二つの式を正確に表現する。葉の初期値から帰納して全F_i、特に根のF_i(0)が正しい。
実装上の注意
- 同値Bでは右端を代表にする。stackで同値もpopする最大Cartesian treeを構成する。
- eventは座標と傾き増分の組で、重み回数だけ展開しない。節約dと傾き−dの符号を混ぜない。
- eventを削る前に、旧savingで区間長×savingを関数値から引く。最後にj_0B_iを加えた値がF_i(0)。
- A_iB_iや各子の和には64bit整数を使う。答えは全体攻撃max A×max B≤10^18を上界にできるが、更新途中も整数幅を確認する。
復習の核
- 葉のF(j)=max(A_i-j,0)B_iから一階差分を描き、親で子の限界節約とB_iが交差するj_0、および同値Bの代表規約を小例で検証する。
計算量と制約
時間
O(N log²(N+1))。各頂点でeventを高々一つ追加し、削除は全体O(N)。同座標も別eventとして保持するmultisetで、小さい方から大きい方へ移す。削除があるので一eventの所属サイズの単調倍増は仮定しない。全eventについてlog₂(所属集合サイズ)の和をpotentialにすると、サイズs≤tの併合は移すs個により少なくともs増加し、サイズmの集合から一eventを削る減少はm log₂m−(m−1)log₂(m−1)=O(log(N+1))。新規追加はpotentialを減らさず、最終potentialもO(N log N)なので、移動総数O(N log N)。一挿入・削除O(log N)、値と傾きの更新は一eventにつきO(1)。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^5; 1 \leq A_i,B_i \leq 10^9; All values in the input are integers.
出典