脳log[20211119]

2021年11月19日 (金) [AtCoder] 精進。PAST202004-N「ビルの建設」。昔は TLE だった>提出 #14165065。まだ BIT を知らなかったのだ。とはいえ当時の日記(20200610p01)を読むと、L 問題を解くために BIT の上位互換であるセグメント木を初めて実装しているのだから、純粋に知らなかったとは言えない。ともあれ今日はささいな記述ミスをいくつか修正しただけで素直に実装完了。座標をゼロ以上にずらしたり圧縮したり、丁寧にやるだけ。提出 #27334595 (AC / 872 Byte / 1105 ms)。■ハッシュ表を使った疎で座圧不要の BIT のアイデアはこたつさんのツイートを通して知りましたよ。だから Y 座標は圧縮したけど X 座標はずらしただけ。元はこれかな>「ふつうの BIT / 要るところだけつくる BIT https://t.co/qcPsZFhhbq」