Codeforces Round 958 (Div. 2)

　Dまで。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 958 (Div. 2) Dまで。
A k-1個ずつ増やせる
B 複数の0を一つに圧縮した後、1の個数>0の個数
C 立っているbit一個を削ったものたちで構成
D 使う回数の最大値が分かれば木DPできる。6回だとWA、大きくするとTLE→20回にしてChatGPTにC++に直してもらったらAC。

— titia (@titia_til) July 15, 2024

E. Range Minimum Sum

　解説AC。こたつがめさんの放送の振り返りも参考にした。

　また、Cartesian Treeはけんちょんさんのブログを参考にした。

　なかなか解説を理解できず、苦労した。

　まず、A[i]を取り除かない場合は、各iに対して、A[i]の左側で、A[i]より初めて小さい値が出てくるindexはどこか？（右側についても同じもの）を調べれば計算できる。

　その上で、差分計算で求めたい。

　このときの差分計算というのは、iを除いた場合とi+1を除いた場合で比較するというもの。全く取り除かない場合と比較するのではない。（結構後者を考えてしまったが、前者が自然ですね）

　そのとき、変更される部分がたいして多くない、というのが重要。取り除くindexがiからi+1へ変更したとき、Cartesian Treeにおいてiの左の子と、そのさらに右の子孫たち（及び、その逆側）、及び、i+1の左の子と、そのさらに右の子孫たち（及び、その逆側）しか変更されない。それらを変更すればOK。

　ただ、どこまで変更すれば良いかもO(1)でできるらしいのだがよく分からず、範囲最小値を求められるSparse tableを使って二分探索で求めた（Segment treeだとTLE）。