本讲定位：CSP-S 选手的 STL 容器”武器库”。J 组层面的
vector/string/stack/queue基础用法见《初赛专题（一）》，本讲不重复，只讲 S 组的增量：有序容器（set/map）、堆（priority_queue）、哈希容器（unordered_map）、位容器（bitset），以及 CCF 考场可用的 GNU 扩展 pb_ds。每个容器回答四个问题：什么时候该用它、复杂度是多少、S 组真题里怎么出现、哪里有坑。前置知识：《初赛专题（一）：STL 容器与线性结构》、结构体与运算符重载、图的邻接表存储。
适合对象：CSP-S 初赛 + 复赛。初赛的阅读程序近年大量使用
set/map/priority_queue；复赛 T1~T2 正确选容器往往就是”会做”与”写得完”的分界线。环境提醒：NOI Linux 2.0 的编译选项是
g++ -O2 -std=c++14。C++17 的结构化绑定（auto [k, v] : mp）、string_view等正式比赛不能用，本讲所有代码均为 C++14 写法。
STL 容器不是背出来的，是按需求选出来的。S 组场上的选型逻辑是一张表：
| 你需要的核心操作 | 首选容器 | 单次复杂度 | 底层结构 |
|---|---|---|---|
| 按下标随机访问、尾部追加 | vector |
$O(1)$ | 动态数组 |
| 维护有序集合：插入/删除/前驱/后继/最值 | set / multiset |
$O(\log n)$ | 红黑树 |
| 键值映射且需要按键有序遍历 | map |
$O(\log n)$ | 红黑树 |
| 键值映射，只查存在性/计数，不关心顺序 | unordered_map |
均摊 $O(1)$ | 哈希表 |
| 反复取最大/最小值 | priority_queue |
$O(\log n)$ | 二叉堆 |
| 大规模 0/1 状态的位运算 | bitset |
$O(n/64)$ | 位压缩数组 |
| 查询第 $k$ 小 / 某数的排名 | pb_ds 的 tree |
$O(\log n)$ | 红黑树+子树大小 |
两条选型口诀：
set/map 比 unordered 慢一个 $\log$，但换来了有序遍历、lower_bound、前驱后继。只做”出现过没有”的判定时才用 unordered。priority_queue 常数远小于 set。set 相对堆的额外能力只有两件事——删除任意元素、查询任意排名位置；用不到就选堆。基础操作不再重复，S 组必须熟练的是 sort + unique + lower_bound 三件套组成的离散化：值域 $10^9$ 装不下数组时，把出现过的值映射成排名 $1 \sim m$。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector<int> a(n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
vector<int> b = a; // 拷贝一份用来做"值 -> 排名"的字典
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end()); // 排序 + 去重，b 就是有序值域
for (int i = 0; i < n; i++) {
int rk = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1; // a[i] 的排名（1 起）
printf("%d ", rk);
}
return 0;
}
lower_bound(first, last, x) 在有序区间里二分出第一个 $\ge x$ 的位置，upper_bound 是第一个 $> x$ 的位置，两者相减就是 $x$ 的出现次数。对 vector 用全局版本没问题（随机访问，$O(\log n)$）；对 set/map 必须用成员版本，原因见 3.4 节。
另外两个 S 组常用细节：
vector<vector<int>> g(n + 1); 建邻接表后，g[u].push_back(v) 加边——比链式前向星好写，O2 下速度足够。reserve(m) 预留容量，可以避免反复搬家（不改变 size()，只影响容量）。emplace_back(a, b) 原地构造元素，装 pair/结构体时比 push_back(make_pair(a, b)) 简洁。