最全、最清晰的 lower_bound / upper_bound 总结，包含：
✔ 功能解释（通俗 + STL 定义）
✔ 返回值含义
✔ 典型代码例子
✔ 在竞赛中的常用技巧
✔ 与 equal_range 的关系
✔ 可视化图示
🔵 1. lower_bound / upper_bound 是什么？
它们是 STL 中的 二分查找算法，要求区间 有序（非降序）。
🔶 2. lower_bound
✔ 定义
iterator lower_bound(iterator first, iterator last, const T& value)
✔ 作用
找到第一个 ≥ value 的位置。
✔ 返回值
- 返回指向 第一个 ≥ value 的迭代器
- 如果不存在，则返回
last
✔ 举例
vector<int> v = {1,2,4,4,4,7,9};
auto it = lower_bound(v.begin(), v.end(), 4);
// it 指向第一个 4（下标 2）
视觉化：
索引: 0 1 2 3 4 5 6
值: 1 2 4 4 4 7 9↑
lower_bound(v, 4) = index 2
🔶 3. upper_bound
✔ 定义
iterator upper_bound(iterator first, iterator last, const T& value)
✔ 作用
找到第一个 > value 的位置。
✔ 返回值
- 返回指向 第一个 > value 的迭代器
- 如果不存在，则返回
last
✔ 举例
auto it = upper_bound(v.begin(), v.end(), 4);
// it 指向 7（下标 5）
视觉化：
索引: 0 1 2 3 4 5 6
值: 1 2 4 4 4 7 9↑
upper_bound(v, 4) = index 5
🔵 4. lower_bound 与 upper_bound 的总结表
| 函数名 | 找到的位置 |
|---|---|
lower_bound(a,a+n,x) |
第一个 ≥ x 的元素 |
upper_bound(a,a+n,x) |
第一个 > x 的元素 |
🔵 5. 典型用法：查找元素出现次数
int cnt = upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x);
例如：v = {1,2,4,4,4,7,9}
查 4：
lower_bound = index 2
upper_bound = index 5
出现次数 = 5 - 2 = 3
🔵 6. 典型竞赛用法
✔ (1) 在有序数组中插入某个值的位置
int pos = lower_bound(a, a+n, x) - a;
✔ (2) 二分查找某个区间内的数量
如查询 (L, R] 区间内有多少个数字：
cnt = upper_bound(v.begin(), v.end(), R)- upper_bound(v.begin(), v.end(), L);
✔ (3) LIS（最长上升子序列）
LIS 模板里就是用 lower_bound 找替换位置。
🔵 7. equal_range = lower_bound + upper_bound
auto p = equal_range(v.begin(), v.end(), x);
// p.first = lower_bound
// p.second = upper_bound
🔵 8. 在 set / multiset 中也能用 lower_bound / upper_bound
例如：
set<int> s = {1, 3, 5, 7};
auto it = s.lower_bound(4); // 指向 5