# 练习 ## 基本使用 ### abc226_b 首先是需要使用 `vector` 记录所有序列。其次，`vector` 支持关系运算符，按照字典序方式进行比较，因此可以将所有序列放入一个 `set` 进行判重。 ### abc236_c 使用 `map` 或 `set` 记录 $M$ 个站点，然后判断 $N$ 个站点是否在集合中。 ### 洛谷 T561134 堆练习 3 使用 `multiset` 模拟，注意删除。 ### 洛谷 T561129 堆练习 2 使用 `multiset` 模拟，注意删除。 ## `lower_bound` 和 `upper_bound` 题目： - CSES 1091 - 洛谷 P5250 结合使用 `lower_bound()` 和 `upper_bound` 查询离 $x$ 最近的元素。 ## 练习 1 ### abc217_d 用一个集合记录所有断点，对于每次查询，查找左右离它最近的两个断点即可得到木棍长度。为了方便查询左右断点，可以一开始将 $0, L$ 加入到集合中。 ### abc241_d 可能有重复元素，使用 `multiset`。 对于 $2$ 操作，找到大于 $x$ 的元素，然后往前找 $k$ 次。 对于 $3$ 操作，找到大于等于 $x$ 的元素，然后往后找 $k - 1$ 次。 注意往前往后查找时，遇到边界迭代器 `.begin()` 和 `.end()` 时处理的细节问题。 ### CSES 1163 我们使用一个 `set` 记录断点（交通信号灯）的位置，每插入一个断点，相当于将原始段删除并新增两个段，因此我们需要再使用一个 `multiset` 维护所有端的长度。 同样地为了方便处理边界，一开始加入断点 $0, x$ 和段长 $x$。 ### CSES 1073 用一个 `multiset` 维护每个塔楼顶的大小。对于每个立方体，贪心地插入到大小比当前立方体大且尽可能小的塔楼顶即可。 实际上，本题求解的是最少下降子序列划分数，根据 Dilworth 定理，即最长不下降子序列长度。 ### CSES 1632 本题端点重合不算区间相交。 本题本质上是你要将尽可能多的区间分成 $k$ 组，使得每组内的区间互不相交。这可以让你联想到两个区间问题：[最多不相交区间](区间类问题/最多不相交区间.md) 和 [区间分组](区间类问题/区间分组.md)。你需要选择哪种排序贪心方式呢？ 答案是选择最多不相交区间问题的贪心策略，我们对所有区间按照右端点排序。我们还需要维护每组区间的结束时间点。 接下来对于每个区间，查找结束时间点在当前区间左端点之前的组，如果有多个组，贪心地找到结束时间点最大的那个组，然后将当前区间放入。 ### 洛谷 T561135 堆练习 4 本题实际上就是对顶堆的加强版。使用两个 `multiset` 代替两个优先队列维护即可。需要证明分界线移动次数是 $O(q)$ 的。 ## 练习 2