parallel binary search・多数境界の判定共有
多数queryの未知境界をmidごとにbucketし、更新を一方向に進める判定器を各roundで共有する。
この典型を扱う単元: parallel binary search・多数境界の判定共有
検索別名: batched monotone search、parallel binary search、simultaneous binary search、並列二分探索
未知問からこの典型を見つける手掛かり
- 扱う対象
- many monotone queries
- shared checker
- threshold events
- 使う手掛かり
- queryごとに最小時刻
- 判定器を共有
- 保つ不変量
- event pointer monotone
- 各queryのlo/hi
- 求めるもの
- 全queryの境界
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
- 単調境界探索: 単一queryの単調境界探索を、多数queryのmidをbucket化して判定器を共有するoffline round処理へ拡張する。
学習成果と学習単位
各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。
parallel binary search・多数境界の判定共有で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。