今日の競プロ(2020/4/22) - gyouzasushi’s diary

解説放送みながらやった。毎週めっちゃ丁寧でめっちゃわかりやすい…。

「色ごとにぼちぼち高速で計算できるのはわかったけどセグ木の初期化に $O(N)$ かかるから結局間に合わないのでは…🤔」になってたけど、新しいセグ木をつくるんじゃなくて逆操作で今までの操作をなかったことにすればいいんか！！確かに〜〜〜。

昨日の。

同符号が連続しているところから一つずつとらないと最長にならない。

$x$ が取りうる値は $2*k$ 以下なので、全探索。

これに似てる。 $a$ → $b$ → $c$ を $a$ → $v$ , $v$ → $b$ , $b$ → $v$ , $v$ → $c$ に分解していい。