ngtkana https://blog.hatena.ne.jp/ngtkana/ ブログ名 https://blog.ngtkana.com/ イントロ Convex hull trick では直線の列を、傾きに関して単調増加になるように管理するのですが、二分探索の検索クエリは傾きだけでは足りません。次のように２種類の二分探索が欲しくなります。 傾きに関して二分探索 最小を達成する区間に関して二分探索 しかしあいにく私はこれを上手にやる方法を知らず、HashMap ２本とかで頑張るしかないかなと思っていました。ただ整合性を担保しないといけないのでバグりやすいですし、（今回は要素が Copy トレイトを実装しているのでそこまで気にしなくてもよいとはいえ）オブジェクトがコピーされるのは Rust 的には気持ちよくはないがちですよね。 そこ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2021%2F12%2F16%2F120841" title="Convex hull trick などの実装に応用のある、Rust の BTreeSet / BTreeMap １本だけで、２通り以上の二分探索を実現する方法 - ブログ名" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-12-16 12:08:41 rich https://blog.ngtkana.com/entry/2021/12/16/120841 1.0 100%