本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-08 20:53:26

set/multiset运用

一、容器特性对比

二、核心操作详解

1. 基础操作

#include <set>
using namespace std;

set<int> s;
multiset<int> ms;

\/\/ 插入元素
s.insert(5);       \/\/ set返回pair<iterator, bool>
ms.insert(5);      \/\/ multiset返回iterator

\/\/ 删除元素
s.erase(5);        \/\/ 删除所有值为5的元素
ms.erase(ms.find(5)); \/\/ 仅删除第一个找到的5

\/\/ 查找操作
auto it = s.find(3);   \/\/ 找不到返回s.end()
int cnt = ms.count(5); \/\/ 统计元素出现次数

\/\/ 范围查找
auto [low, high] = s.equal_range(4); \/\/ 获取等于4的元素区间

\/\/ 特殊访问
s.begin();        \/\/ 最小元素
s.rbegin();       \/\/ 最大元素（反向迭代器）

2. 高级操作

\/\/ 合并集合（C++17）
set<int> s1, s2;
s1.merge(s2);  \/\/ 将s2元素移动到s1，重复元素保留在s2

\/\/ 提取节点（C++17）
auto nh = s.extract(3); \/\/ 获取节点但不复制
s.insert(move(nh));     \/\/ 重新插入

\/\/ 自定义排序规则
struct cmp {
    bool operator()(const string& a, const string& b) const {
        return a.length() < b.length();
    }
};
set<string, cmp> lengthSet;

三、经典例题解析

例题1：洛谷P1177 【模板】排序（去重排序）

题目要求：对n个数字进行升序排序并去重

set实现：

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n, x;
    set<int> s;
    cin >> n;
    while(n--) {
        cin >> x;
        s.insert(x);
    }
    cout << s.size() << endl;
    for(auto v : s) cout << v << " ";
    return 0;
}

例题2：AtCoder ABC212C - Min Difference

题目要求：在两个数组中找到最小差值

multiset优化解法：

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

int main() {
    int n, m, x;
    multiset<int> s;
    
    cin >> n >> m;
    for(int i=0; i<n; ++i) {
        cin >> x;
        s.insert(x);
    }
    
    int ans = INT_MAX;
    while(m--) {
        cin >> x;
        auto it = s.lower_bound(x);
        if(it != s.end()) ans = min(ans, *it - x);
        if(it != s.begin()) ans = min(ans, x - *prev(it));
    }
    cout << ans << endl;
    return 0;
}

例题3：洛谷P3369 【模板】普通平衡树

功能需求：

1. 插入x
2. 删除x（若有多个相同元素，只删除一个）
3. 查询x的排名
4. 查询排名为x的数
5. 求x的前驱
6. 求x的后继

multiset实现：

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

multiset<int> ms;

int get_rank(int x) {
    return distance(ms.begin(), ms.lower_bound(x)) + 1;
}

int get_num(int k) {
    auto it = ms.begin();
    advance(it, k-1);
    return *it;
}

int main() {
    int q, op, x;
    cin >> q;
    while(q--) {
        cin >> op >> x;
        switch(op) {
        case 1: ms.insert(x); break;
        case 2: ms.erase(ms.find(x)); break;
        case 3: cout << get_rank(x) << endl; break;
        case 4: cout << get_num(x) << endl; break;
        case 5: 
            auto it = ms.lower_bound(x);
            cout << *(--it) << endl;
            break;
        case 6:
            cout << *ms.upper_bound(x) << endl;
            break;
        }
    }
    return 0;
}

四、进阶应用技巧

1. 维护动态中位数

https://www.luogu.com.cn/problem/U207461

题目要求：依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

multiset<int> left, right; \/\/ 左半部大顶堆，右半部小顶堆

void insert(int x) {
    if(left.empty() || x <= *left.rbegin()) 
        left.insert(x);
    else 
        right.insert(x);
    
    \/\/ 平衡两个集合
    if(left.size() > right.size()+1) {
        right.insert(*left.rbegin());
        left.erase(prev(left.end()));
    } else if(right.size() > left.size()) {
        left.insert(*right.begin());
        right.erase(right.begin());
    }
}

\/\/ 获取中位数
int get_median() {
    return *left.rbegin();
}

2. 离散化处理

\/\/ 使用set进行离散化
vector<int> arr = {5, 3, 9, 3, 7};
set<int> s(arr.begin(), arr.end());
unordered_map<int, int> mapping;
int idx = 1;
for(int v : s) mapping[v] = idx++;

五、练习题推荐

1. 洛谷P1059 明明的随机数（set去重排序）
2. 洛谷P2073 送花（multiset维护双关键字）
3. AtCoder ABC245D - Polynomial division（multiset维护多项式系数）
4. 洛谷P2286 [HNOI2004]宠物收养所（平衡树应用）
5. 洛谷U207461 动态维护中位数(用set实现对顶堆)
6. Codeforces 706D - Vasiliy's Multiset（异或操作+multiset维护）

六、常见错误与优化

典型错误案例

\/\/ 错误1：迭代器失效
set<int> s = {1,2,3};
for(auto it=s.begin(); it!=s.end(); ++it) {
    if(*it == 2) s.erase(it); \/\/ erase后it失效
}

\/\/ 正确写法
auto it = s.find(2);
if(it != s.end()) s.erase(it);

\/\/ 错误2：错误删除所有元素
multiset<int> ms = {1,1,2};
ms.erase(1); \/\/ 删除所有1，留下size=1

\/\/ 正确删除单个元素
ms.erase(ms.find(1));

性能优化技巧

1. 使用emplace_hint优化插入：

auto hint = s.end();
for(int x : data) {
    hint = s.emplace_hint(hint, x);
}

2. 批量操作优化：

vector<int> temp{5,2,8,3};
s.insert(temp.begin(), temp.end()); \/\/ 优于循环插入

3. 利用有序性进行范围查询：

\/\/ 统计[L, R]区间内的元素数量
int count = distance(s.lower_bound(L), s.upper_bound(R));