set 是 STL 中一种标准关联容器。它底层使用平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，所以效率比较高。set，顾名思义是“集合”的意思，在 set 中元素都是唯一的，而且默认情况下会对元素自动进行升序排列，支持集合的交(set_intersection),差(set_difference) 并(set_union)，对称差(set_symmetric_difference) 等一些集合上的操作，如果需要集合中的元素允许重复那么可以使用 multiset。

这题考了STL的使用——set。

T3 踮脚顾盼梨园

A1kiTA.png

set 的常用操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//头文件
    #include<set>

//定义
    set<int> S;//定义一个set
    set<int>::iterator it//定义一个迭代器

//插入
    S.inster(2);//插入元素2
    S.inster(1);//插入元素1
    S.inster(3);//插入元素3

//删除
    //删去集合里的元素:3
        it=S.find(3);
        S.erase(it);
        //S.erase(3); 也可以直接这么删除元素:3
    //清空容器
        S.clear()

//修改
    //修改就是删除再插入。

//查找
    //查找2这个元素
        S.find(2);//返回为一个迭代器,若找不到则返回S.end()
    //输出集合内元素
        for (it=S.begin();it!=S.end;++it){
            printf("%d ",*it);
        }

//其他
    //判断集合是否为空
        S.empty();
    //输出集合内元素个数
        printf("%d\n",S.size());
    //返回第一个大于或等于给定关键值的元素
        s.lower_bound();
    //返回第一个大于给定关键值的元素
        s.upper_bound();

本题代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<set>
#define ll long long
using namespace std;
inline ll read() {
    ll ans=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') {f=-1;}ch=getchar();}
    while(ch>='0'&&ch<='9') {ans=ans*10+ch-48;ch=getchar();}
    return ans*f;
}
void write(ll x){
    if(x<0){putchar('-');x=-x;}
    if(x>9){write(x/10);}
    putchar(x%10|48);
}
struct node{
    int l,r;
    bool operator <(const node &oth)const{
        return r<oth.l;//重载小于号为右端点与左端点的大小关系 
    }
};
set<node> S; //"set"容器，为集合，实现方式为红黑树,是一种自平衡二叉查找树。它的查找，删除，插入时间为O(log n) 
set<node>::iterator it;//iterator迭代器，用来访问set容器 
char opt;
int n;
int main() {
    freopen("shi.in","r",stdin);
    freopen("shi.out","w",stdout);
    n=read();
    while(n--){
        scanf(" %c",&opt);
        if(opt=='A'){
            int ans=0;
            int l=read(),r=read();//区间长度 
            node temp=(node){
                l,r
            };
            for (it=S.find(temp);it!=S.end();it=S.find(temp)){//find函数用于返回一个迭代器，当这个元素与temp这个元素重合时，若为空返回容器末尾迭代器'S.end' 
                S.erase(it);//弹出该元素 
                ans++;//统计弹出元素数量 
            }
            S.insert(temp);//插入该元素 
            write(ans);
            puts("");
        }else{
            write(S.size());//S.size为该容器内元素个数。 
            puts("");
        }
    }
    return 0;
}