第 3.8 章：映射与集合

3.8.0 从一道题出发：牛的编号

先看一道典型的 Silver 风格题：

🐄 题目：独特的奶牛 有 N（N ≤ 10⁵）头奶牛，每头有一个编号 id_i（范围可达 10⁹，且可能是负数）。 农夫 John 想知道：

1. 有多少个不同的编号？
2. 哪个编号出现次数最多？（并列输出最小的编号）
3. 给 Q 次查询，每次问「编号严格大于 x 的不同编号有几个？」

先试试你会的方法

问题 1、2 用数组计数？ 编号范围 10⁹ 还有负数——开 cnt[10⁹] 数组直接内存爆炸。而且编号本身没有上限，说明值域不能当下标用。

问题 3 用排序 + 二分？ 排序后「大于 x 的个数」确实是二分。但若题目是边插入边查询（在线），每次重排一遍就是 O(NQ log N)，超时。我们需要一个始终有序、支持动态插入的结构。

问题 1、2 的另一种直觉： 「编号 → 出现次数」天然是一个映射；「出现过哪些编号」天然是一个集合。C++ 的 map/set 就是把「值域任意的东西」变成可以 O(log N) 存取的东西——数组的下标是 0..N-1，而 map 的「下标」可以是任何可比较的值。

拆解这道题需要回答的问题

1. map 的频率统计（问题 1、2）已在第 3.1.3 节学过，本章直接用
2. 有序性到底带来了什么别人做不到的能力？→ 3.8.1 回顾与选型
3. 问题 3 需要「动态有序集」——set 的 lower_bound 怎么用？→ 3.8.2 有序操作
4. 多重集合（同一编号出现多次都要保留）呢？→ 3.8.6 multiset
5. USACO 真题里怎么出现？→ 3.8.4 真题与本章练习

3.8.1 回顾：从 map/set 到「动态有序」

第 3.1.3 节已经教过 map 和 set 的基本操作（插入、查找、erase、有序遍历，以及 map[key] 自动创建的陷阱）。本节不重复这些内容，而是补上 3.1 没有讲的部分：这两个容器内部长什么样，以及它们真正的杀手锏——动态维护有序性。

内部结构决定了能力：

• map / set 内部是红黑树（平衡 BST）：插入/查找 O(log N)，元素始终有序——这是 unordered_map 做不到的。
• unordered_map / unordered_set 内部是哈希表：平均 O(1) 更快，但无序。（原理与防 hack 见第 3.7 章。）

有序性带来的三个杀手锏（本章的主角）：

1. *s.begin() / *s.rbegin() 随时取最小/最大值——O(1)；
2. lower_bound(x) / upper_bound(x) 动态二分查找——插入和查询交替进行也不会超时；
3. 遍历即有序输出——不需要额外排序。

📌 什么时候必须用 map/set 而不是 unordered_： 需要有序遍历、需要取最值、需要 lower_bound 动态查询，或担心被 hack（见 3.7.2）。只需纯查找时，unordered_ 更快。

回到开头的问题 3：「编号严格大于 x 的不同编号有几个？」——把所有编号存进 set，答案就是 s.end() - s.upper_bound(x)，且边插入边查询也没问题。这就是 3.1 学不到、本章要练的能力。

3.8.2 set 的有序操作——lower_bound 动态查询

3.1 只展示了 set 的去重用途。真正区分新手和熟手的，是 lower_bound / upper_bound 与动态插入的组合：

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s = {5, 3, 8, 1, 9, 2};
    // s = {1, 2, 3, 5, 8, 9}（始终有序！）

    // 动态二分查询（set 内置的版本，不是 <algorithm> 的）
    auto it = s.lower_bound(4);  // 第一个 >= 4 的元素
    cout << *it << "\n";         // 5

    auto it2 = s.upper_bound(4); // 第一个 > 4 的元素
    cout << *it2 << "\n";        // 5

    // 边插边查——排序数组做不到，set 可以
    s.insert(4);
    cout << *s.lower_bound(4) << "\n";   // 4（刚插入就生效）

    // ⚠️ 陷阱：set 迭代器是双向迭代器，不能相减！
    // s.end() - s.upper_bound(3)  ← 编译错误！

    // 计数「> 3 的元素有几个」的正确姿势：distance（O(log N) 之后还要 O(k) 步进，慎用于大区间）
    cout << distance(s.upper_bound(3), s.end()) << "\n";  // 4（4, 5, 8, 9）

    return 0;
}

⚠️ 重要陷阱： vector 排序后可以直接 upper_bound(v.begin(), v.end(), x) - v.begin() 拿下标，但 set 的迭代器是双向迭代器，- 无法编译。要么用 std::distance（复杂度与步数成正比），要么改用 order_of_key（见下面的扩展）。

3.8.4 USACO 题目：奶牛 ID

题目（USACO 2017 February Bronze）： 给定一组「已占用」的 ID 集合和 N，找第 N 个可用的 ID。

数据规模： 1 ≤ 已占用 ID 数 ≤ 10⁴，1 ≤ 查询数 Q ≤ 10⁴，1 ≤ ID ≤ 10⁹（ID 范围太大，不能开布尔数组）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    set<int> taken;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        taken.insert(x);
    }

    // 对每个查询 q，找第 q 个不在 taken 中的正整数
    while (q--) {
        int k; cin >> k;

        // 二分查找：找最小的 x 使得 x - (x 以内已占用的数量) >= k
        int lo = 1, hi = 2e9;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            // [1, mid] 中可用数量 = mid - (≤ mid 的已占用数量)
            int taken_count = (int)(taken.lower_bound(mid + 1) - taken.begin());
            int available = mid - taken_count;
            if (available >= k) hi = mid;
            else lo = mid + 1;
        }

        cout << lo << "\n";
    }

    return 0;
}

3.8.6 Multiset——允许重复的有序集合

multiset 类似于 set，但允许重复值：

#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> ms;
    ms.insert(3);
    ms.insert(1);
    ms.insert(3);   // 允许重复
    ms.insert(5);
    ms.insert(1);

    // ms = {1, 1, 3, 3, 5}

    cout << ms.count(3) << "\n";  // 2（有几个 3）
    cout << ms.count(2) << "\n";  // 0

    // 只移除一个 3
    ms.erase(ms.find(3));  // 只移除一个 3
    // ms = {1, 1, 3, 5}

    // 移除所有的 1
    ms.erase(1);  // 移除所有 1
    // ms = {3, 5}

    cout << *ms.begin() << "\n";   // 3（最小）
    cout << *ms.rbegin() << "\n";  // 5（最大）

    return 0;
}

用两个 Multiset 维护动态中位数

用最大 multiset（下半部分）和最小 multiset（上半部分）跟踪数据流的中位数：

#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> lo;  // 下半部分（rbegin() = 最大值）
    multiset<int> hi;  // 上半部分（begin() = 最小值）

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        // 加入合适的半部分
        if (lo.empty() || x <= *lo.rbegin()) {
            lo.insert(x);
        } else {
            hi.insert(x);
        }

        // 重新平衡：大小差不超过 1
        while (lo.size() > hi.size() + 1) {
            hi.insert(*lo.rbegin());
            lo.erase(lo.find(*lo.rbegin()));
        }
        while (hi.size() > lo.size()) {
            lo.insert(*hi.begin());
            hi.erase(hi.begin());
        }

        // 打印中位数
        if (lo.size() == hi.size()) {
            // 偶数个：两个中间值的平均
            double median = (*lo.rbegin() + *hi.begin()) / 2.0;
            cout << fixed << setprecision(1) << median << "\n";
        } else {
            // 奇数个：中间值在 lo 中
            cout << *lo.rbegin() << "\n";
        }
    }

    return 0;
}

3.8.7 进阶：pb_ds ——会数数的红黑树

痛点： 「集合中第 k 小的值是多少？」「严格小于 x 的元素有几个？」——set 做不到（迭代器不能相减，见 3.8.2），map 也做不到。排序数组可以做但每次插入 O(N)。

GCC 内置的 pb_ds 库提供了一个自带排名的平衡树，两个操作都是 O(log N)：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// 竞赛通用模板：直接抄
template<class T>
using ordered_set = tree<T, null_type, less<T>,
                         rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    int n, q;
    cin >> n >> q;
    ordered_set<int> s;
    for (int i = 0; i < n; i++) { int x; cin >> x; s.insert(x); }

    while (q--) {
        string op; int x;
        cin >> op >> x;
        if (op == "k") {          // 第 k 小（1-indexed）
            if (x < 1 || x > (int)s.size()) cout << "invalid\n";
            else cout << *s.find_by_order(x - 1) << "\n";
        } else {                  // 严格小于 x 的元素个数
            cout << s.order_of_key(x) << "\n";
        }
    }
    return 0;
}

两个核心方法：

样例输入：

5 3
3 1 4 1 5
k 2
rank 4
rank 1

样例输出：

3
2
0

（去重后 s = {1, 3, 4, 5}：第 2 小是 3；小于 4 的有 1、3 共 2 个；小于 1 的没有。）

典型用法（USACO Gold 常见）：

• 动态第 k 小：边插入边查询——排序数组做不到；
• 区间计数：「值在 [l, r] 内的元素个数」= order_of_key(r+1) - order_of_key(l)；
• 配对 pair 用 less_equal 可以当可删除的多重集合——multiset 删不了「第 k 小」，它删得了。

⚠️ 注意： pb_ds 是 GCC 扩展，USACO / Codeforces（GCC 编译器）都支持，但 MSVC 等编译器没有。本地用 clang + Apple SDK 时也可能没有这个头文件——竞赛代码不受影响，本地测试需要换 GCC。

3.8.8 实用模式

模式一：统计不同元素

vector<int> data = {1, 5, 3, 1, 2, 5, 5, 3};
set<int> distinct(data.begin(), data.end());
cout << "不同值的个数：" << distinct.size() << "\n";  // 4

模式二：按频率分组，按值排序

vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
map<int, int> freq;
for (int x : nums) freq[x]++;

// 按频率分组
map<int, vector<int>> byFreq;
for (auto &[val, cnt] : freq) {
    byFreq[cnt].push_back(val);
}

// 按频率顺序打印
for (auto &[cnt, vals] : byFreq) {
    for (int v : vals) cout << v << "（×" << cnt << "）\n";
}

模式三：离线查询与排序结合

将查询与事件一起排序，以 O((N+Q) log N) 一起处理：

// 示例：对每个查询点，统计有多少事件的值 <= 查询点
// 对两个数组排序，用双指针扫描

⚠️ 第 3.8 章常见错误

本章总结

📌 核心要点

🧩 「用哪个容器」速查

❓ 常见问题

Q1：map 的 [] 运算符和 find 有什么区别？

A：m[key] 当键不存在时会自动创建默认值（int 的默认值为 0）；m.find(key) 只查找，不创建。如果只想检查键是否存在，用 m.count(key) 或 m.find(key) != m.end()。

Q2：multiset 和 priority_queue 都能取极值——用哪个？

A：priority_queue 只能取极值并删除，不支持按值删除。multiset 支持查找并删除任意值，更灵活。只需反复取极值时，priority_queue 更简单；需要删除特定元素（如滑动窗口移除离开的元素）时，用 multiset。

Q3：unordered_map 什么时候比 map 慢？

A：哈希碰撞严重时退化到 O(N)（包括被对手针对性构造数据）。原因与防法见第 3.7.2 节。

Q4：C++17 结构化绑定 auto &[key, val] 安全吗？竞赛中能用吗？

A：USACO 和大多数竞赛平台支持 C++17，for (auto &[key, val] : m) 可以安全使用。比 entry.first/entry.second 更简洁。

🔗 与后续章节的联系

• 第 3.3 章（排序与搜索）：坐标压缩常与 map 结合（值 → 压缩后下标）
• 第 5.7 章（线段树）：有序 set 的 lower_bound 可以替代简单的线段树查询
• 第 5.1–5.2 章（图）：map 常用于存储稀疏图的邻接表
• 第 4 部分（贪心）：multiset 结合贪心策略可以高效维护动态最优选择
• map 频率统计模式贯穿全书，是竞赛编程中最基础的工具之一

练习题

题目 3.8.1 — 字母异位词分组 🟡 中等 将 N 个单词按其字母排序后的形式分组。

数据规模： 1 ≤ N ≤ 10⁴，1 ≤ 单词长度 ≤ 100，均由小写字母组成。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    map<string, vector<string>> groups;
    for (int i = 0; i < n; i++) {
        string w; cin >> w;
        string key = w; sort(key.begin(), key.end());
        groups[key].push_back(w);
    }
    for (auto& [key, words] : groups) {
        sort(words.begin(), words.end());
        for (const string& w : words) cout << w << " ";
        cout << "\n";
    }
}

复杂度： O(N × K log K)，K = 平均单词长度。

题目 3.8.2 — 区间最大重叠数 🟡 中等 统计 N 个区间在点 1..M 上的最大重叠数。

数据规模： 1 ≤ N ≤ 10⁵，1 ≤ M ≤ 10⁶，1 ≤ L ≤ R ≤ M。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, M; cin >> n >> M;
    vector<int> diff(M + 2, 0);
    for (int i = 0; i < n; i++) {
        int l, r; cin >> l >> r;
        diff[l]++; diff[r+1]--;
    }
    int cur = 0, ans = 0;
    for (int i = 1; i <= M; i++) {
        cur += diff[i];
        ans = max(ans, cur);
    }
    cout << ans << "\n";
}

复杂度： O(N + M)。

题目 3.8.4 — 奶牛摄影 🔴 困难 找与所有 N 个列表（每个都是 ID 的一个排列）一致的顺序。

数据规模（与 USACO 2011 原题「Cow Photography」一致）： 1 ≤ N ≤ 20,000，1 ≤ K ≤ 5，ID 为 1..N 的排列。

核心思路： 对每对 (a, b)，统计 a 在多少个列表中排在 b 之前。若 a 在超过一半的列表中排在 b 前面，则 a 在真实顺序中排在 b 前面。用这个成对比较来排序。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<vector<int>> pos(k, vector<int>(n+1));
    for (int i = 0; i < k; i++)
        for (int j = 0; j < n; j++) {
            int x; cin >> x; pos[i][x] = j;
        }
    vector<int> cows(n); iota(cows.begin(), cows.end(), 1);
    sort(cows.begin(), cows.end(), [&](int a, int b){
        int before = 0;
        for (int i = 0; i < k; i++) before += (pos[i][a] < pos[i][b]);
        return before > k / 2;
    });
    for (int c : cows) cout << c << "\n";
}

题目 3.8.6 — 实时不同值计数 🟢 简单 每读入一个新整数后，打印到目前为止见过的不同值的个数。

数据规模： 1 ≤ N ≤ 10⁶，-10⁹ ≤ A[i] ≤ 10⁹。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    unordered_set<int> seen;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        seen.insert(x);
        cout << seen.size() << "\n";
    }
}

复杂度： O(N) 均摊。