#include<set>

头文件 set 主要包含 set 和 multiset 两个容器，分别是“有序集合”和“有序多重集”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set 和 multiset 的内部实现是一颗红黑树（平衡树的一种），它们支持的函数基本相同。

定义

set<int> s;

struct node{ 
//...
};
set<node>s;

multiset<double> s;

与优先队列一样，set 和 multiset 存储的元素**必须定义"小于号"**运算符。

size()/empty()/clear()

与 vector 类似，分别为元素个数、是否为空、清空。前两者的时间复杂度为 $O(1)$。

迭代器

set 和 multiset 的迭代器成为“双向访问迭代器”，不支持“随机访问”，支持星号（*）解除引用，仅支持“++”和“--”两个与算术相关的超作。（不存在两个迭代器相减，获得迭代器之间的距离几个元素的用法，之前线性结构容器有这种方法）

设 it 是一个迭代器，例如 set<int>::iterator it;

若把 it++,则 it 会指向“下一个”元素。 这里的“下一个”是指在元素从小到大排序的结果中，排在 it 下一名的元素。同理，若把 it--，则 it 将会指向排在“上一个”的元素。

请注意，执行“++”和“--”操作的时间复杂度都是 $O(\log{n})$. 执行操作前后，务必仔细检查，避免迭代器的位置超出首、尾迭代器之间的范围。

begin()/end()

返回集合的首、尾迭代器，时间复杂度为 $O(1)$.

s.begin() 是指向集合中最小元素的迭代器。

s.end() 是指向集合中最大元素的下一个位置的迭代器。换言之，就像 vector 一样，是一个“前闭后开”的形式。因此 --s.end() 是指向集合中最大元素的迭代器。

insert()

s.insert(x) 把一个元素 x 插入到集合 s 中，时间复杂度为 $O(\log{n})$.

在 set 中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。

下面的代码把 $n$ 个数插入有序多重集 multiset ,并从小大输出，时间复杂度为 $O(\log{n})$.

muliset<int>s;
for( int  i=1; i<=n ; i++)s.insert(a[i]);
for(multiset<int>::iterator it=s.begin();it!=s.end();it++)
     cout<<(*it)<<" ";
//C++11之后
for(int x : s)
    cout<<x<<" ";
for(auto it=s.begin();it!=s.end();it++)
    cout<<(*it)<<" ";

find()

s.find(x) 在集合 s 中查找等于 x 的元素，并返回指向该元素的迭代器。若不存在，则返回 s.end()。时间复杂度为 $O(\log{n})$.

lower_bound()/upper_bound()

这两个函数的用法与 find 类似，但查找的条件略有不同，时间复杂度为 $O(\log{n})$

s.lower_bound(x) 查找 s 中第一个大于等于 x 的元素，返回指向该元素的迭代器。

s.upper_bound(x) 查找 s中第一个大于x的元素，返回指向该元素的迭代器。

erase

设 it 是一个迭代器，s.erase(it) 从 s 中删除迭代器 it 指向的元素，时间复杂度为 $O(\log{n})$.

设 x 是一个元素，s.erase(x) 从 s 中删除所有等于 x 的元素，时间复杂度为 $O(k+\log{n})$,其中 $k$ 为被删除的元素个数。

如果想从muliset中删掉至多 1 个等于 x 的元素，可以执行： if((it=s.find(x))!=s.end())s.earse(it);

count

s.count(x) 返回集合 s 中等于 x 的元素个数，时间复杂度为 $O(k+\log{n})$，其中 k 为元素 x 的个数。

---

【例1】：[CSP-J 2024] 扑克牌

思路：可以利用 set 去重。

【例2】： [ZJOI2007] 报表统计

思路：可以使用 vector 维护第 $i$ 个位置插入的数，使用 multiset 维护相邻两个数的差。当新插入一个数时，要删除之前相邻两个数的差，然后插入新的差。

要维护全局相邻最小，可以再使用 multiset 维护。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
int n,m;
int Gap2;
vector<int>g[N];
multiset<int>st,ans;
int Pre1(int x)    //前驱
{
    auto it=st.lower_bound(x);
    if(it!=st.begin())
    {
        it--;
        return *it;
    }
    return -2e9;
}
int Suc1(int x)   //后继
{
    auto it=st.lower_bound(x);
    if(it!=st.end())
        return *it;
    return 2e9;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;  cin>>x;
        g[i].push_back(x);
        st.insert(x);
    }

    Gap2=2e9;
    for(int i=2;i<=n;i++)
        ans.insert(abs(g[i][0]-g[i-1][0]));
    Gap2=*ans.begin();

    int lst=2e9;
    for(int x:st)
        Gap2=min(Gap2,abs(x-lst)),lst=x;
    
    while(m--)
    {
        string s;
        cin>>s;
        if(s[0]=='I')
        {
            int i,a;
            cin>>i>>a;

            int pre,suc;
            pre=g[i][g[i].size()-1];
            if(i<n)
            {
                suc=g[i+1][0];
                auto it=ans.lower_bound(abs(pre-suc));
                ans.erase(it);   //删除之前的差
                ans.insert(abs(pre-a));
                ans.insert(abs(suc-a));                
            }
            else ans.insert(abs(pre-a));
            
            Gap2=min(Gap2,min(abs(Pre1(a)-a),abs(Suc1(a)-a)));
            
            g[i].push_back(a);
            st.insert(a);
        }
        else if(s=="MIN_GAP")cout<<*ans.begin()<<"\n";
        else cout<<Gap2<<"\n";
    }
    return 0;
}

学习完毕

{{ select(1) }}

• YES
• NO