今日解いた競プロの問題。

ABC165-F: LISはセグ木を使って$O(N\log N)$で求められるが、当然全ての頂点について$O(N\log N)$かければTLEする。

LISを求めるアルゴリズムの中身を考えると、1つ次の要素を考えるたびにセグ木の高々1か所を更新しているだけなので、これはメモっておけば簡単に戻すことができる。dfsでオイラーツアーしていけば、各頂点について2回セグ木を更新するだけ(追加と戻し)で済むので$O(N\log N)$で解ける。

$a_i$が大きいので座圧する必要があることだけ注意。ちゃんと考えたら思ったより簡単だった。

---

今週の胎界主を読んだ。何これ？何これ？

「理性を保っている」「記憶が混在している」というところから、一応主人格は元の人間っぽい？？？それとも主人格という概念すら曖昧なくらいにぐちゃぐちゃに混ざった精神になっている？？？(元)九狼と(元)徳は大暴れするみたいな気はないようだが、北斗は何起こすか全くわからん。

ここまで意味わからん状況になるとは思わなかった。こっからの流れとしてはどこかの時点で徳が言うように悪魔が殲滅部隊を送ってくるか、それより先にレックスが焼却しに来るか。というかそれ以前にイノッチは明日からどんな顔して九狼と顔合わせるんだ…

久しぶりに出たヘイスティングスの絵がピースしていて良かった。もう死んでるけど。

---

昨夜は久々にちゃんと早く寝た。生活習慣を直していきたい。