This is a library of policy-based elementary data structures: associative containers and priority queues. It is designed for high-performance, flexibility, semantic safety, and conformance to the corresponding containers in std and std::tr1 (except for some points where it differs by design).
using namespace __gnu_pbds;//前面双下划线

一、hash（速度快的恐怖）。
http://codevs.cn/problem/1230/

#include<stdio.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
__gnu_pbds::gp_hash_table<int, bool> gf;
inline int in()
{
    int res=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-48,c=getchar();
    return res;
}
int main()
{
    int n = in(), m = in(), x;
    while(n--){
        x = in();
        gf[x] = true;
    }
    while(m--){
        x = in();
    puts(gf[x] ? "YES" : "NO");
    }
    return 0;
}

二、堆（先跳过）
三、平衡树（不用自己写了太好了吧）
rb_tree_tag（红黑树）
splay_tree_tag（伸展树）
tree_order_statistics_node_update（增加名次树功能）
例如：
tree, rb_tree_tag, tree_order_statistics_node_update> T;
操作：
1、order_of_key(x)//返回有多少个数小于x
2、find_by_order(x)//理解为有x个数比某数小，并返回这个数的迭代器。
3、lower_bound
4、insert
5、erase
6、a.split(v,b)//key小于等于v的元素属于a，其余的属于b
https://www.luogu.org/problemnew/show/P3369

1、插入 xxx 数
2、删除 xxx 数(若有多个相同的数，因只删除一个)
3、查询 xxx 数的排名(排名定义为比当前数小的数的个数 +1+1+1 。若有多个相同的数，因输出最小的排名)
4、查询排名为 xxx 的数
5、求 xxx 的前驱(前驱定义为小于 xxx ，且最大的数)
6、求 xxx 的后继(后继定义为大于 xxx ，且最小的数)

#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;
typedef long long ll;
__gnu_pbds::tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> T;
inline ll in()
{
    ll res=0,p=1;
    char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') p=-1; c=getchar();};
    while(c>='0'&&c<='9') res=res*10+c-48,c=getchar();
    return p*res;
}
int main()
{
    ll n = in(), opt, x;
    for (ll i = 0; i < n; ++i){
    opt = in(), x = in();
        //因为只能删除一个数，所以不同次插入的相同的数的值要不同
    if (opt == 1) T.insert((x << 17) + i);
        else if (opt == 2) T.erase(T.lower_bound(x << 17));
        else if (opt == 3) printf("%d\n", T.order_of_key(x << 17) + 1);
        //查询第x个数要find_by_order(x - 1)
        else if (opt == 4) printf("%lld\n", *T.find_by_order(x - 1) >> 17);
        else if (opt == 5) printf("%lld\n", *--T.lower_bound(x << 17) >> 17);
        else printf("%lld\n", *T.lower_bound((x + 1) << 17) >> 17);
    }
    return 0;
}

4、trie（找不到资料，先跳过）

这玩意的部分操作可以用树状数组实现。
话说我用这个写题的时候发现了个很诡异的事情，就是T的函数的参数的数据类型一定要本来就是ll，不能强制类型转换也不能隐式类型转换，否则就是错的，所以能ll就ll就好了，一定要注意。