2021/07/12
やる気もあまりなかったかな
競プロ
AtCoder: 3問
その他
Baba Is Youを買った
ロンド・ロンド・ロンドをみた
atcoder.jp 上位K個の和を管理するデータ構造を書いたほうがいいのかなという気がしている(マニュアルには遅延評価と書いてあるんだけど遅延評価の概念がよくわかってないからちょっと写経してみるか...)
atcoder.jp
↑の長方形１個バージョンがAOJにあって(↓)これは かかるので(ちなみにしたに貼ったコードは最大長方形とその範囲も返してくれるスグレモノですverify済)、そんなに取れる方針がなくて、はじめは貪欲で一つずつ取るのを考えたけどこれはサンプル3みたいなので壊れる。x軸かy軸で２つの長方形は分断できるということに気づくと, 左右から解いて累積maxができるということがわかった
