ngtkana https://blog.hatena.ne.jp/ngtkana/ ブログ名 https://blog.ngtkana.com/ 問題 ARC 164 E - Segment-Tree Optimization 解法 mark がひとつもないとき（つまりすべてのクエリが全体クエリのとき）は特別で、答えは $(0, q)$ となりますが、そうでないときを考えましょう。 区間 $[l, r[$ に対するクエリが来るたびに、$[l - 1, l + 1[$ を含む節点全てに mark し、また $[r - 1, r + 1[$ を含む節点全てにも mark することにします。このとき mark の深さの最大値を $d$、深さ $d$ の mark の個数の最小値を $c$ とおくと、答えは $(1 + d, 2c)$ の最小値… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2024%2F11%2F29%2F231518" title="ARC 164 E - Segment-Tree Optimization の別解法（Knuth–Yao speedup） - ブログ名" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/n/ngtkana/20241129/20241129180221.png Hatena Blog https://hatena.blog 2024-11-29 23:15:18 rich https://blog.ngtkana.com/entry/2024/11/29/231518 1.0 100%