Sen_comp https://blog.hatena.ne.jp/Sen_comp/ Senの競技プログラミング備忘録 https://sen-comp.hatenablog.com/ Codeforces データ構造 スライド最小値 deque 典型 蟻本 codeforces.com 概要 n行m列の行列がある。それからa行b列の部分行列を切り出す。(n-a+1) * (m-b+1)個できる。部分行列の項の最小値の和を(n-a+1)*(m-b+1)個分足した値を答えよ。 ただし、n行m列の行列はとして、である。制約: 1 ACするまで 1. 与式で構築された行列、数学的な規則を利用して解くのはなさそう。 2. 典型を感じる。2次元セグメント木でいけそう(後述) 3. 1次元ならば、サイズ固定なのでスライド最小値で行けそう。でも2次元。。。 4. よく考えてみたらスライド最小値は軸ごとに独立。2回やればいいので終わり->AC! 考察 このスライド… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsen-comp.hatenablog.com%2Fentry%2F2019%2F12%2F27%2F222926" title="Codeforces Round #574 - E. OpenStreetMap - Senの競技プログラミング備忘録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20a_%7Bij%7D%3Dg_%7Bi%2A%28n-1%29%2Bj%7D Hatena Blog https://hatena.blog 2019-12-27 22:29:26 rich https://sen-comp.hatenablog.com/entry/2019/12/27/222926 1.0 100%