STL set
例题：P5250 【深基17.例5】木材仓库
分析：这个问题可以抽象为：维护一个集合，可以插入一个元素 \(x\)，同时判断 \(x\) 是否已经存在；查询 \(x\) 的前驱后继，\(x\) 的前驱定义为小于 \(x\) 的最大的数，\(x\) 的后继定义为大于 \(x\) 的最小的数；可以删除指定元素
STL 中的 set 可以很方便地解决这个问题，set 的本质是红黑树（一种比较优秀的平衡二叉查找树）
使用 set 需要通过 #include <set> 引入相应头文件，其常用方法如下：
set<int> s创建一个名字叫做 s 的、元素类型为 int 的集合s.insert(x)在集合中删除元素 \(x\)，如果这个数不存在，则什么都不干，时间复杂度为 \(O(\log n)\)s.erase(x)在集合中删除元素 \(x\)，如果这个数不存在，则什么都不干，时间复杂度为 \(O(k+\log n)\)，其中 \(k\) 为被删除掉的元素个数s.erase(it)删除集合中迭代器 it 指向的元素，时间复杂度为 \(O(\log n)\)s.end()返回集合中最后一个元素的下一个元素的迭代器，很少直接使用，通常配合其他方法进行比较，以确认某个元素是否存在s.find(x)如果 \(x\) 不在集合中，返回 s.end()，否则返回指向元素 \(x\) 的迭代器s.lower_bound(x)查询大于等于 \(x\) 的最小的元素在集合中对应的迭代器，如果没有这样的元素，返回 s.end()s.uppper_bound(x)查询大于 \(x\) 的最小的元素在集合中对应的迭代器，如果没有这样的元素，返回 s.end()s.empty()如果集合是空的，返回 true，否则返回 falses.size()返回集合中元素的个数
迭代器： set 中的迭代器是一种“双向访问迭代器”，不支持“随机访问”，支持星号“*”解引用（即获取迭代器对应的元素值），仅支持“++”和“--”这两个与算术相关的操作。
设 it 是一个迭代器，例如 set<int>::iterator it;
若把 it++，则 it 将会指向“下一个”元素。这里的“下一个”是指在元素按从小到大的顺序中，排在 it 下一名的元素。同理，若把 it--，则 it 会指向排在“上一个”的元素。执行操作前后，务必仔细检查，避免迭代器指向的位置超出首、尾迭代器的范围。
本题中进货操作可以直接在集合中用 insert()，查询操作可以用 lower_bound() 操作实现，出货删除操作可以使用 erase() 实现，lower_bound 返回的是仓库中大于等于要求长度的最短的木棍，所以还需要和比这根还短一些的那根木棍来比较一下，看看哪根木棍离要求的木棍长度更接近。
参考代码
#include <cstdio>
#include <set>
using namespace std;
int main()
{set<int> s;int m; scanf("%d", &m);while (m--) {int op, len; scanf("%d%d", &op, &len);if (op == 1) {if (s.find(len) != s.end()) printf("Already Exist\n");else s.insert(len);} else { if (s.size() == 0) {printf("Empty\n"); continue;}auto iter = s.lower_bound(len); // 这里的iter实际上是set<int>::iterator类型// 迭代器类似于指针 *iter 解引用if (iter == s.end()) { // 说明最大的都没有len大iter--; printf("%d\n", *iter); s.erase(iter);} else if (iter == s.begin()) { // 说明最小的都大于等于len，等于说没有前一个元素了printf("%d\n", *iter); s.erase(iter);} else {auto tmp = iter; tmp--; // 因此如果iter是s.begin()，没法--if (len - *tmp <= *iter - len) {printf("%d\n", *tmp); s.erase(tmp);} else {printf("%d\n", *iter); s.erase(iter);}}}}return 0;
}
习题：P2286 [HNOI2004] 宠物收养场
解题思路
题意涉及到找出一个序列中与 \(x\) 差值最小的数，而且数据保证读入的数值不重复，可以用 set 维护特点值。
同一时间在收养所中的要么全是宠物，要么全是领养者。如果读入的是宠物，当前没有领养者，则向维护宠物特点值的 set 中插入，反之则肯定有领养者可以和宠物配对。接下来用 lower_bound 找出最接近特点值的元素，选择大于等于的最小值和小于的最大值中更优的那一个配对（注意特判边界情况），更新答案，并删去对应元素。读入领养者和读入宠物没有本质区别，因此可以将配对过程抽成函数，减少代码量。
参考代码
#include <cstdio>
#include <set>
using namespace std;
typedef long long LL;
const int MOD = 1000000;
void find_closest(set<int>& s, int key, int& ans) {auto iter = s.lower_bound(key);if (iter == s.end()) {--iter; ans += (key - *iter); ans %= MOD; s.erase(iter);} else if (iter == s.begin()) {ans += (*iter - key); ans %= MOD; s.erase(iter);} else {auto tmp = iter; tmp--;if (key - *tmp <= *iter - key) {ans += (key - *tmp); ans %= MOD; s.erase(tmp);} else {ans += (*iter - key); ans %= MOD; s.erase(iter);}}
}
int main()
{int n;scanf("%d", &n);set<int> pet, adopter;int ans = 0;while (n--) {int a, b; scanf("%d%d", &a, &b);if (a == 0) {if (adopter.size() > 0) find_closest(adopter, b, ans);else pet.insert(b);} else {if (pet.size() > 0) find_closest(pet, b, ans);else adopter.insert(b);}}printf("%d\n", ans);return 0;
}
STL multiset
multiset 是一个允许元素重复的、自动排序的集合容器，同 set 一样，它的底层也通常用红黑树实现。
#include <iostream>
#include <set>
#include <string>
using namespace std;
// 辅助函数，用于打印 multiset 的状态
void print_multiset_status(multiset<int>& ms, const string& message) {cout << "--- " << message << " ---\n";if (ms.empty()) {cout << "Multiset is empty.\n\n";return;}cout << "Content: { ";for (int val : ms) {cout << val << " ";}cout << "}\n";cout << "Smallest element (begin): " << *ms.begin() << "\n\n";
}
int main()
{// 1. 创建 multisetmultiset<int> ms;print_multiset_status(ms, "Initial state");// 2. 插入 (insert)ms.insert(40);ms.insert(20);ms.insert(50);ms.insert(20); // 插入重复值ms.insert(40);print_multiset_status(ms, "After inserting {40, 20, 50, 20, 40}");// 3. 查找 (find)cout << "--- Finding elements ---\n";auto it_20 = ms.find(20);if (it_20 != ms.end()) {cout << "Found '20'. Iterator points to: " << *it_20 << "\n";} auto it_99 = ms.find(99);if (it_99 == ms.end()) {cout << "Did not find '99', find() returned end().\n";}cout << "\n";// 4. 删除 (erase)// 4.1 按迭代器删除一个 '20'ms.erase(it_20);print_multiset_status(ms, "After erasing ONE '20' using an iterator");// 4.2 按值删除所有 '40'ms.erase(40);print_multiset_status(ms, "After erasing ALL '40's by value");// 5. lower_boundms.insert(30);ms.insert(30);print_multiset_status(ms, "After inserting two '30's");cout << "--- Using lower_bound ---\n";auto lb = ms.lower_bound(25); // 查找第一个 >= 25 的元素if (lb != ms.end()) {cout << "The first element not less than 25 is: " << *lb << "\n";}cout << "\n";// 6. 清空 (clear)cout << "--- Clearing the multiset ---\n";ms.clear();print_multiset_status(ms, "After calling clear()");return 0;
}
习题：CF1889C1 Doremy's Drying Plan (Easy Version)
解题思路
首先考虑暴力做法。
对于每一个位置 \(i=1,2,3,...,n\) 可以通过差分与前缀和预处理每个位置被线段覆盖的次数。首先，对于每个覆盖次数为 \(0\) 的位置，可以放到最后再考虑，因为这部分点的数量与移除的两条线段无关，设这部分点的数量为 \(A\)，再设移除两条线段后产生的新的不被覆盖的点的数量是 \(B\)，则本题的答案为 \(A + \max B\)。
要计算 \(B\)，考虑每一对线段 \(I_1, I_2\)：
- 如果两者不交叉，\(B\) 等于 \(I_1\) 和 \(I_2\) 中刚好覆盖一次的点的数量之和；
- 如果两者交叉，假设两者交叉的线段为 \(J\)，则 \(B\) 等于\(I_1\) 和 \(I_2\) 中刚好覆盖一次的点的数量之和再加上 \(J\) 中恰好覆盖两次的点的数量。
如果直接枚举每一对线段，则时间复杂度为 \(O(n + m^2)\)，考虑优化这个算法：
- 对于两线段不交叉的情况，实际上直接从所有线段中挑出覆盖一次的点的数量最多的两条即可；
- 对于两线段交叉的情况，实际上真正有用的最多只有 \(n\) 对线段：对于每一个位置 \(i\)，如果它恰好被覆盖两次，此时就考虑覆盖这个点的两条线段即可。
对于某一个点，如何维护覆盖它的线段？这里我们可以把每个线段 \([l,r]\) 看成是在 \(l\) 位置开始计算时引入，在 \(r\) 位置完成计算后移除，可以利用一个 multiset 来维护当前涉及到的线段，这样一来时间复杂度优化到 \(O(n+m \log m)\)。
参考代码
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 200005;
// left[i]: 存储所有左端点为 i 的区间的右端点
// right[i]: 存储所有右端点为 i 的区间的左端点
vector<int> left[N], right[N];
// diff: 差分数组
// cnt[i]: 城市 i 被覆盖的次数
// sum1[i]: cnt值为1的城市数量的前缀和
// sum2[i]: cnt值为2的城市数量的前缀和
int diff[N], cnt[N], sum1[N], sum2[N];
// s: 存储当前活跃的区间 {l, r}
multiset<pair<int, int>> s;
int main()
{int t; scanf("%d", &t);while (t--) {int n, m, k; scanf("%d%d%d", &n, &m, &k); // k=2 in this version// --- 初始化 ---for (int i = 1; i <= n + 1; i++) {left[i].clear(); right[i].clear();diff[i] = 0;}// --- 读入区间并构建差分数组 ---for (int i = 1; i <= m; i++) {int l, r; scanf("%d%d", &l, &r);left[l].push_back(r); right[r].push_back(l);diff[l]++; diff[r + 1]--;}// --- 计算每个城市的覆盖次数 cnt 和前缀和 sum1, sum2 ---for (int i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + diff[i];for (int i = 1; i <= n; i++) {sum1[i] = sum1[i - 1]; sum2[i] = sum2[i - 1];if (cnt[i] == 1) sum1[i]++;else if (cnt[i] == 2) sum2[i]++;}// --- 策略一：取消两个不相交的区间 ---// 目标是找到两个区间，它们各自解放的 cnt=1 的城市数之和最大int max1 = 0, max2 = 0; // 记录解放 cnt=1 城市数最多的和次多的for (int i = 1; i <= n; i++) for (int x : left[i]) { // 遍历每个区间 [i, x]int cur = sum1[x] - sum1[i - 1];if (cur > max1) {max2 = max1; max1 = cur;} else if (cur > max2) max2 = cur;}int ans = max1 + max2; // 策略一的候选答案// --- 策略二：取消两个可能相交的区间 ---s.clear();for (int i = 1; i <= n; i++) {// 将所有以 i 为左端点的区间加入活跃集合 sfor (int x : left[i]) s.insert({i, x});// 如果当前城市 i 被恰好两个区间覆盖if (cnt[i] == 2) {// 这两个区间一定是活跃集合 s 中左端点最小的两个auto it = s.begin();int l1 = it->first, r1 = it->second;it++;int l2 = it->first, r2 = it->second;// a,b,c,d 是 l1,r1,l2,r2 排序后的结果// [a,d] 是并集，[b,c] 是交集int points[] = {l1, r1, l2, r2};sort(points, points + 4);int a = points[0], b = points[1], c = points[2], d = points[3];// 计算收益：(并集内的cnt=1城市数) + (交集内的cnt=2城市数)// sum1[d] - sum1[a-1] 是并集内的cnt=1城市数// sum2[c] - sum2[b-1] 是交集内的cnt=2城市数ans = max(ans, sum1[d] - sum1[a - 1] + sum2[c] - sum2[b - 1]);}// 将所有以 i 为右端点的区间移出活跃集合 sfor (int x : right[i]) s.erase(s.find({x, i}));}// --- 最终结果 ---// 加上原本就干燥的城市 (cnt[i]==0) for (int i = 1; i <= n; i++) if (cnt[i] == 0) ans++;printf("%d\n", ans);}return 0;
}
习题：P1110 [ZJOI2007] 报表统计
解题思路
题目描述的 INSERT i k 是在第 i 个原始元素相关的块之后插入。因为只有块头和块尾会影响到相邻元素的差值，可以使用两个数组 a 和 b，a 存储初始序列（块头），b 数组则用来存储每个块的最后一个元素。当执行 INSERT i k 时，实际上是将 k 插入到 b[i] 和 a[i+1] 之间，然后 k 成为了这个块新的最后一个元素，所以更新 b[i] = k 即可。
MIN_GAP 是序列中所有相邻元素差的绝对值中的最小值。当执行 INSERT i k 时，序列的变化是：... a[i], ..., b[i], a[i+1], ... 变成了 ... a[i], ..., b[i], k, a[i+1], ...。因此，旧的差值 |b[i] - a[i+1]| 需要被移除。两个新的差值 |b[i] - k| 和 k - a[i+1] 需要被加入。可以用 multiset 存储所有这些差值，并快速提供最小值。
MIN_SORT_GAP 是所有数值中最接近的两个数的差。这个值与元素在序列中的位置无关。当一个新值 k 被加入序列时，它可能会创造一个新的最小差值，这个新差值只会出现在 k 和它在所有数值的有序排列中的前驱与后继之间。可以用 multiset 维护序列中所有数字的有序集合。用一个整型变量存储当前已知的最小值。在程序开始时，完整计算一次初始的 MIN_SORT_GAP。当 INSERT i k 发生时，检查 k 与其前驱和后继形成的差值，用以更新最小值，再将 k 加入到存储所有序列数值的 multiset 中。
参考代码
#include <iostream>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
const int N = 5e5 + 5;
const int INF = 1e9;
// a[] 存储初始序列，之后不再改变
// b[i] 存储与原始第 i 个元素关联的“块”的最后一个元素的值
int a[N], b[N];
int main()
{int n, m; cin >> n >> m;// gap: 使用 multiset 存储所有相邻元素的差值// num: 使用 multiset 存储序列中所有的数字，保持有序multiset<int> gap, num;// --- 初始化 ---for (int i = 1; i <= n; i++) {cin >> a[i]; b[i] = a[i]; // 初始时，每个块的最后一个元素就是它自己if (i > 1) gap.insert(abs(a[i] - a[i - 1]));num.insert(a[i]);}// 计算初始的 MIN_SORT_GAPint min_sort_gap = INF, pre = -1;for (int x : num) {if (pre != -1) {min_sort_gap = min(min_sort_gap, x - pre);}pre = x;}// --- 处理 m 次操作 ---for (int t = 1; t <= m; t++) {string op; cin >> op;if (op == "INSERT") {int i, k; cin >> i >> k;// --- 更新 gap (相邻差值) ---// 1. 移除旧的差值 |b[i] - a[i+1]|// b[i] 是第 i 个块的最后一个元素，a[i+1] 是下一个块的第一个元素if (i < n) {gap.erase(gap.find(abs(b[i] - a[i + 1])));}// 2. 插入新差值 |b[i] - k| 和 |k - a[i+1]|gap.insert(abs(b[i] - k));if (i < n) { // 只有当不是在序列末尾插入时，才有 a[i+1]gap.insert(abs(a[i + 1] - k));}// 3. 更新第 i 个块的最后一个元素为 kb[i] = k;// --- 更新 min_sort_gap ---// 1. 在有序集合 num 中找到新值 k 要插入的位置auto iter = num.lower_bound(k);// 2. 检查 k 与其后继的差值if (iter != num.end()) {min_sort_gap = min(min_sort_gap, *iter - k);}// 3. 检查 k 与其前驱的差值if (iter != num.begin()) {iter--;min_sort_gap = min(min_sort_gap, k - *iter);}// 4. 将新值 k 插入有序集合 numnum.insert(k);} else if (op == "MIN_GAP") {cout << *gap.begin() << "\n";} else { // MIN_SORT_GAPcout << min_sort_gap << "\n";}}return 0;
}
STL map
例题：P5266 【深基17.例6】学籍管理
这样的学籍管理系统也是一个集合，但是功能更加复杂，需要根据索引找到对应的元素，并对这些元素进行操作。可以通过使用 STL 里面的 map 来解决这个问题。
map 关联集合的本质也是一棵红黑树，可以看作是一个下标可以是任意类型的数组。其头文件是 map，可以调用 map 实现如下几个基础功能：
map<A, B> mp：建立一个名字叫做mp，下标类型为A，元素类型为B的映射表，例如map<string, int>就是一个将string映射到int的映射表。这种映射结构俗称“键-值对”。mp[A] = B：把这个“数组”中下标为A的位置的值变成B，这里下标可以是任意类型，不一定限定为大于 0 的整数，比如map<string, string> mp，就可以进行mp["username"] = "password"的操作。mp[A]：访问这个“数组”中下标为A的元素，比如可以进行cout << mp["username"] << "\n";这样的操作。mp.end()：返回映射表中最后一个元素的下一个元素的地址，这个很少单独使用，而是配合其他方法进行比较，以确认某个元素是否存在。mp.find(x)：查询x在映射表中的地址，如果这个数不存在，则返回mp.end()。mp.empty()：如果映射表是空的，则返回true，否则返回false。mp.size()：返回映射表中的元素个数。mp.erase(A)：删除这个“数组”中下标为A的元素。注意：在使用mp[A]访问“数组”下标为A的元素时，如果这个下标对应的元素不存在，则会自动创建下标为A、值为默认值（例如，所有数值类型的默认值是 0，string类型是空字符串）的元素。
#include <iostream>
#include <string>
#include <map> // 包含 map 头文件
using namespace std;
// sys 是一个 map 容器，用于存储学籍信息
// 键(key)是 string 类型的学生姓名
// 值(value)是 int 类型的学生分数
map<string, int> sys;
int main()
{int n; cin >> n; // 操作的总次数for (int i = 0; i < n; ++i) {int op; cin >> op; // 操作类型if (op == 1) {// --- 操作 1: 插入或修改 ---string name;int score; cin >> name >> score;// 使用 map 的 [] 操作符// 如果 name 已存在，则更新其对应的分数为 score// 如果 name 不存在，则插入一个新的键值对 {name, score}sys[name] = score;cout << "OK\n";} else if (op == 2) {// --- 操作 2: 查询 ---string name; cin >> name;// 使用 map 的 find 方法查找是否存在键为 name 的元素// find 返回一个迭代器。如果找不到，返回 map.end()if (sys.find(name) != sys.end()) {// 如果找到了，输出其对应的分数cout << sys[name] << "\n";} else {// 如果没找到，按要求输出cout << "Not found\n";}} else if (op == 3) {// --- 操作 3: 删除 ---string name; cin >> name;// 同样，先用 find 检查是否存在if (sys.find(name) == sys.end()) {// 如果不存在，输出 "Not found"cout << "Not found\n";} else {// 如果存在，使用 erase 方法删除该键值对sys.erase(name);cout << "Deleted successfully\n";}} else { // op == 4// --- 操作 4: 汇总 ---// 使用 map 的 size 方法获取当前元素的数量cout << sys.size() << "\n";}}return 0;
}