2316. 星际补给站的精准对接
1000ms
256MB
简单
二分算法
题目描述
给定一个长度为 $N$ 的有序递增序列 $A$（包含 $N$ 个正整数）。现有 $M$ 次询问，每次询问给出一个目标值 $K$ 和一个查询类型 $T$：
- 若 $T = 1$：求序列中第一个**大于等于** $K$ 的元素的下标。
- 若 $T = 2$：求序列中第一个**严格大于** $K$ 的元素的下标。
**注意**：下标从 1 开始计数。如果序列中不存在满足条件的元素，请输出 $N + 1$。
输入格式
- 第一行包含两个正整数 $N$ 和 $M$ ($1 \le N, M \le 10^5$)。
- 第二行包含 $N$ 个有序递增的正整数 $a_i$ ($1 \le a_i \le 10^9$)。
- 接下来 $M$ 行，每行包含两个正整数 $T$ 和 $K$ ($T \in \{1, 2\}, 1 \le K \le 10^9$)。
输出格式
- 输出共 $M$ 行，每行一个整数，对应每次询问的答案。
样例 1
输入 (Input)
6 4 1 3 3 5 7 9 1 3 2 3 1 6 1 10
输出 (Output)
2 4 5 7
- 对于 $100\%$ 的数据：$N, M \le 10^5$，序列元素和 $K$ 均在 `int` 范围内（建议使用 `long long` 以防万一）。
- **函数解析**：
- `lower_bound(begin, end, K)`：返回指向第一个**大于等于** $K$ 的元素的迭代器。
- `upper_bound(begin, end, K)`：返回指向第一个**严格大于** $K$ 的元素的迭代器。
- **效率提示**：由于询问次数较多，请使用 $O(\log N)$ 的二分查找，并注意 I/O 优化。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功