挙動
lower_bound
: xs[i] ≥ key
となる最小の i
を求めるupper_bound
: xs[i] > key
となる最小の i
を求めるi
が存在しない場合は xs[i].len()
を返す)解釈
[1, 3, 5, 5, 6, 7]
[----)
L U
lower_bound で混乱している人かわいそう - えびちゃんの日記
key と同じ値が [lower_bound, upper_bound)
の範囲にある
配列上の切り捨てと切り上げ
条件を満たす範囲の大きさを求める
条件を満たすギリギリの値を求める
ABC362 G - Count Substring Query
2つの数列A, B が与えられたとき
A[i] + B[j] <= S
となる (i, j)
の個数A[j] + B[j] <= S
となる最小の A[j] + B[j]
の値など
B をソート後、A全探索→B二分探索
半分全列挙後に使うこともある。