NISHIO Hirokazu[Translate]
条件付き最大値を対数オーダーで求める
2つの数列Ai, Biが与えられる。Biがxを超えない最大のAiを見つけたい。
単発であれば線形オーダーで見つけられるが、xを変えて繰り返されるので前処理をして対数オーダーにしたい。

(Ai, Bi)を辞書順ソートし、Bj>BiでAj<=Aiであるようなjを取り除く。それらが解になることはないから。
取り除いた列に対して二分探索でBiがxを超えない最大のiを見つければよい。

蟻本p.149

Related Pages

  • →最大流×最大流を求めるアルゴリズムの歴史×蟻本×最大二部マッチング→
  • Dinic
  • →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitdp×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×sparse_table×rmq×atcoder→
  • プログラミングコンテストチャレンジブック
  • →abc180×巡回セールスマン問題×tsp×bitdp×蟻本→
  • ABC180E
  • →蟻本×binary_lndexed_tree×bit×fenwick_tree×値域と定義域の交換×multiset×座標圧縮×データ構造→
  • フェニック木
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]