定義
- $\operatorname{lower\_bound}(A, k)$: $A_i \geq k$ となる最小の $i$
- $\operatorname{upper\_bound}(A, k)$: $A_i > k$ となる最小の $i$
- (そういう $i$ が存在しない場合は $A$ の長さを返す)
解釈
[1, 3, 5, 5, 6, 7]
[----)
L U
lower_bound で混乱している人かわいそう - えびちゃんの日記
key と同じ値が [lower_bound, upper_bound) の範囲にある
Rust の superslice では [lower_bound, upper_bound) を求める関数として、equal_range がある。
各値の lower_bound と upper_bound
$i$ での upper_bound $=$ $i+1$ での lower_bound になっている（定義から明らかではある）
lower_bound, upper_bound の典型問題
数列 $A,B$ は昇順でソートされているとする。
- step1
- $A_i \geq k$ となる最小の $i$: $\operatorname{lower\_bound}(A, k)$
- $A_i > k$ となる最小の $i$: $\operatorname{upper\_bound}(A, k)$
- $A_i \leq k$ となる最大の $i$: $\operatorname{upper\_bound}(A, k) -1$
- $A_i < k$ となる最大の $i$: $\operatorname{lower\_bound}(A, k) -1$
- $A_i \in [l, r)$ となる $i$ の範囲: $[\operatorname{lower\_bound}(A, l), \operatorname{lower\_bound}(A, r))$
- $A_i \in [l, r]$ となる $i$ の範囲: $[\operatorname{lower\_bound}(A, l), \operatorname{upper\_bound}(A, r))$
- $A_i =k$ となる $i$ の範囲: $[\operatorname{lower\_bound}(A, k), \operatorname{upper\_bound}(A, k))$
- step2
- $A_i \in [l, r)$ となる $i$ の数: $\operatorname{lower\_bound}(A, r)- \operatorname{lower\_bound}(A, l)$
- $A_i \geq k$ となる $i$ の数: $\lvert A \rvert - \operatorname{lower\_bound}(A, k)$
- $A_i \geq k$ となる最小の $A_i$: $A_{\operatorname{lower\_bound}(A, k)}$
- step3
- $A_i + B_j \leq k$ をみたす $(i, j)$ の数
- 各 $i$ に対して、 $B_j \leq K - A_i$ となる $j$ の数を求めればよい
- 計算量: $O(|A| \log |B|)$
- (足し算の代わりにかけ算のパターンもあり得る）
- $A_i + B_j \leq k$ をみたす最大の $A_i + B_j$
- 各 $i$ に対して、$B_j \leq k - A_i$ をみたす最大の $B_j$ を求めれば良い
- 計算量: $O(|A| \log |B|)$
- (足し算の代わりにかけ算のパターンもあり得る）
- $\sum_{i=1}^N \min\{A_i, x\}$
- ソートして累積和とって二分探索
- $\sum_{i=1}^N \operatorname{clamp}(A_i, l, r)$
- これもソートして累積和とって二分探索でよい。
- $A_i + B_j \leq k$ をみたす $(i, j)$ の数
配列上の切り捨てと切り上げ
その他
- equal_range_by_key
- 半分全列挙との親和性