LGJの无人之境

1
## 技巧          ← 二级标题（大分区）
2
### lower_bound  ← 三级标题（具体知识点）

1
**第一个 ≥ L 的位置**

1
`lower_bound` 复杂度 `O(log n)`

1
```cpp
2
auto it = upper_bound(a.begin(), a.end(), L);
3
int cnt = a.end() - it;
4
```
5
5. 列表
6

7
- 第一点
8
- 第二点
9
6. 数学公式（KaTeX）
10
行内：$O(\log n)$　独立：$$a_{n+1} = a_n + d$$
11

12
例子：lower_bound 与 upper_bound
13
lower_bound：第一个 ≥ L 的位置（第一个不小于 L 的）
14
upper_bound：第一个 > L 的位置（第一个严格大于 L 的）
15

16
upper_bound(a.begin(), a.end(), L)
17
// 返回第一个严格大于 L 的元素的迭代器（一个"指针"）
18
int cnt = a.end() - upper_bound(a.begin(), a.end(), L);
19
// a.end() 指向数组末尾，减去"第一个大于 L 的位置"，得到大于 L 的元素个数
20
两个函数都是二分查找，复杂度 $O(\log n)$。
21

22

23

24
---