ACM-ICPC 中可能会使用到的库

sort(v.first(),v.end(),cmp())
unique(v.first(),v.end(),cmp()) 第三个参数可以传入一个bool型，用来判断是不是相等，返回unique后的超尾
max_element(v.first(),v.end(),cmp()) 返回一个迭代器
max_element(v.first(),v.end(),cmp()) 返回一个迭代器
nth_elemtn(v.first(),v.first()+nth,v.end(),cmp()) 对整个容器部分排序后，返回nth迭代器。其中 $[first,nth)$ 都比nth小， $[nth,last)$ 都不小于nth。

reverse(v.first(),v.end())反转
rotate(v.first(),v.middle(),v.end()) 左右交换位置，用处不大还慢（因为随机访问对CPU缓存机制的不友好，太差劲了）
random_shuffle(first, last, rand)产生随机序列

pb_ds

//首先需要以下头文件以及命名空间 #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds;

优先队列
#include <ext/pb_ds/priority_queue.hpp>

可合并优先队列pairing_heap_tag
此外，pb_ds库的优先队列支持合并操作，pairing_heap的合并时间复杂度是O(logn)的，可以说基本上完美代替了左偏树。合并的调用方式是：

支持迭代器，可以记录push的返回迭代器来对优先队列中的元素进行修改

join(priority_queue &other) //合并两个堆,other会被清空
split(Pred prd,priority_queue &other) //分离出两个堆
modify(point_iterator it,const key) //修改一个节点的值

因为重名的原因一定要加上 __gnu_pbds::
__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> pq;
// 对两优先队列进行一些操作
a.join(b);（O(1)合并）
　　此时优先队列b内所有元素就被合并进优先队列a中，且优先队列b被清空。

名次树/红黑树

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

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> rbtree;

// int类型

// null_type为映射类型, 低版本g++为 null_mapped_type// less<int>, greater<int> 比较器// rb_tree_tag 和 splay_tree_tag 选择树的类型// tree_order_statistics_node_update 结点更新// insert, erase// order_of_key rank// find_by_order() kth// lower_bound() 前继， >=x 最小的迭代器// upper_bound() 后继 >x 最小的迭代器// a.join(b) b并入a，前提是两颗树的取值范围不相交// a.split(v, b) key <= v的属于a，其他属于// 注意，插入的元素会去重，如set

迭代器支持++和--
计数从0开始而不是从1开始，例如查询第k+1小的数，使用find_by_order()函数，返回的为迭代器。t.find_by_order(2)，查询（常说的第3小的数）
查询比x小的数的个数，注意，是比x小的个数，不是x的排名。t1.order_of_key(2)，查询比2小的数的个数，相当于2的排名-1。

正常的splay

#include <ext/pb_ds/tree_policy.hpp>#include <ext/pb_ds/assoc_container.hpp>#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
const int MAXN = 1000000 + 10;
int price, menu[MAXN], cnt[MAXN];
template<class T>inline bool nextInt(T &n) {
    T x = 0, tmp = 1;
    char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF)
        c = getchar();
    if(c == EOF)
        return false;
    if(c == '-')
        c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9')
        x *= 10, x += (c - '0'), c = getchar();
    n = x*tmp;
    return true;
}
template<class T>inline void Out(T n) {
    if(n < 0) {
        putchar('-');
        n = -n;
    }
    int len = 0, data[20];
    while(n) {
        data[len++] = n%10;
        n /= 10;
    }
    if(!len)
        data[len++] = 0;
    while(len--)
        putchar(data[len]+48);
}

struct Splay_Tree {
    struct Node {
        int father, childs[2], key, cnt, _size;
        inline void init() {
            father = childs[0] = childs[1] = key = cnt = _size = 0;
        }        inline void init(int father, int lchild, int rchild, int key, int cnt, int sz) {
            this -> father = father, childs[0] = lchild, childs[1] = rchild;
            this -> key = key, this -> cnt = cnt, _size = sz;
        }
    } tre[MAXN];
    int sign, root;
    inline void init() {
        sign = root = 0;
    }
    inline bool judge(int x) {
        return tre[ tre[x].father ].childs[1] == x;
    }
    inline void update(int x) {
        if(x) {
            tre[x]._size = tre[x].cnt;
            if(tre[x].childs[0]) {
                tre[x]._size += tre[ tre[x].childs[0] ]._size;
            }
            if(tre[x].childs[1]) {
                tre[x]._size += tre[ tre[x].childs[1] ]._size;
            }
        }
    }
    inline void rotate(int x) {
        int y = tre[x].father, z = tre[y].father, k = judge(x);
        //tre[y].childs[k] = tre[x].childs[!k], tre[ tre[x].childs[!k] ].father = y;        //tre[x].childs[!k] = y, tre[y].father = x;        //tre[z].childs[ tre[z].childs[1] == y ] = x, tre[x].father = z;
        if(k == 0) { ///zig            tre[y].childs[0] = tre[x].childs[1], tre[ tre[x].childs[1] ].father = y;            tre[x].childs[1] = y, tre[y].father = x;        } else { ///zag            tre[y].childs[1] = tre[x].childs[0], tre[ tre[x].childs[0] ].father = y;            tre[x].childs[0] = y, tre[y].father = x;        }        tre[z].childs[ tre[z].childs[1] == y ] = x, tre[x].father = z;
            update(y);
        }
        inline void splay(int x,int goal) {
            for(int father; (father = tre[x].father) != goal; rotate(x) ) {
                if(tre[father].father != goal) {
                    rotate(judge(x) == judge(father) ? father : x);
                }
            }
            root = x;
        }
        inline void insert_node(int x) {
            if(root == 0) {
                tre[++sign].init(0, 0, 0, x, 1, 1);
                root = sign;
                return ;
            }
            int now = root, father = 0;
            while(1) {
                if(tre[now].key == x) {
                    tre[now].cnt ++;
                    update(now), update(father);
                    splay(now, 0);
                    break;
                }
                father = now;
                if(x > tre[now].key) {
                    now = tre[now].childs[1];
                } else {
                    now = tre[now].childs[0];
                }
                if(now == 0) {
                    tre[++sign].init(father, 0, 0, x, 1, 1);
                    if(x > tre[father].key) {
                        tre[father].childs[1] = sign;
                    } else {
                        tre[father].childs[0] = sign;
                    }
                    update(father);
                    splay(sign, 0);
                    break;
                }
            }
        }
        inline int pre() {
            int now = tre[root].childs[0];
            while(tre[now].childs[1]) {
                now = tre[now].childs[1];
            }
            return now;
        }
        inline int next() {
            int now = tre[root].childs[1];
            while(tre[now].childs[0]) {
                now = tre[now].childs[0];
            }
            return now;
        }
        inline int find_rank(int x) { /// 找x的排名        int now = root, ans = 0;        while(1) {            if(x < tre[now].key) {                now = tre[now].childs[0];            } else {                if(tre[now].childs[0]) {                    ans += tre[ tre[now].childs[0] ]._size;                }                if(x == tre[now].key) {                    splay(now, 0);                    return ans + 1;                }                ans += tre[now].cnt;                now = tre[now].childs[1];            }        }    }
            inline int find_by_order(int x) {
                int now = root;
                while(1) {
                    if(tre[now].childs[1] && x <= tre[ tre[now].childs[1] ]._size ) {
                        now = tre[now].childs[1];
                    } else {
                        int rchild = tre[now].childs[1], sum = tre[now].cnt;
                        if(rchild) {
                            sum += tre[rchild]._size;
                        }
                        if(x <= sum) {
                            int ans = tre[now].key;
                            splay(now, 0);
                            return ans;
                        }
                        x -= sum;
                        now = tre[now].childs[0];
                    }
                }
            }
            inline int find_rankx(int x) { /// 找排名为x的数字        int now = root;        while(1) {            if(tre[now].childs[0] && x <= tre[ tre[now].childs[0] ]._size ) {                now = tre[now].childs[0];            } else {                int lchild = tre[now].childs[0], sum = tre[now].cnt;                if(lchild) {                    sum += tre[lchild]._size;                }                if(x <= sum) {                    return tre[now].key;                }                x -= sum;                now = tre[now].childs[1];            }        }    }
                inline void del(int x) {
                    find_rank(x);
                    if(tre[root].cnt > 1) {
                        tre[root].cnt --;
                        update(root);
                        return ;
                    }
                    if(!tre[root].childs[0] && !tre[root].childs[1]) {
                        tre[root].init();
                        root = 0;
                        return ;
                    }
                    if(!tre[root].childs[0]) {
                        int old_root = root;
                        root = tre[root].childs[1], tre[root].father = 0, tre[old_root].init();
                        return ;
                    }
                    if(!tre[root].childs[1]) {
                        int old_root = root;
                        root = tre[root].childs[0], tre[root].father = 0, tre[old_root].init();
                        return ;
                    }
                    int pre_node = pre(), old_root = root;
                    splay(pre_node, 0);
                    tre[root].childs[1] = tre[old_root].childs[1];
                    tre[ tre[old_root].childs[1] ].father = root;
                    tre[old_root].init();
                    update(root);
                }
                inline bool find(int x) {
                    int now = root;
                    while(1) {
                        if(now == 0) {
                            return 0;
                        }
                        if(x == tre[now].key) {
                            splay(now, 0);
                            return 1;
                        }
                        if(x > tre[now].key) {
                            now = tre[now].childs[1];
                        } else {
                            now = tre[now].childs[0];
                        }
                    }
                }
            }
            tre;
            int n, opt, x;
            int main() {
                scanf("%d", &price);
                int id = 1;
                while(nextInt(opt) && opt) {        //scanf("%d", &x);        nextInt(x);        if(opt == 1) { /// add price of x            tre.insert_node(x);            cnt[x]++;       /// 价格x的菜的数量            menu[id++] = x; /// 第id道菜价格x            continue;        }        if(opt == 2) {            int p = menu[x];            tre.find(p);            if(cnt[p]) {                cnt[p]--;            }            continue;        }        if(opt == 3) {            int res = tre.find_by_order(x);            if(res > price) {                puts("Dui bu qi,Mei you.");            } else if(cnt[res] == 0) {                puts("Mei you. Zhe ge ke yi you. Zhe ge zhen mei you!");            } else {                printf("You. %d Yuan.
", res);            }        }    }

                    return 0;
                }

View Code

平衡树
pb_ds库这次内置了红黑树（red-black tree）、伸展树（splay tree）和排序向量树（ordered-vector tree，没找到通用译名，故自行翻译）。这些封装好的树都支持插入（insert）、删除（erase）、求kth（find_by_order）、求rank（order_of_key）操作

封装好的红黑树可以达到手写Treap的速度。

求kth（find_by_order）返回的是迭代器，求rank返回的是值，两者都是从0开始计算的。

此外，它们也支持合并（join）和分离（split）操作。用法如下。

tree<int,null_type> a,b;
// 对两平衡二叉树进行一些操作
a.join(b);
// 对两平衡二叉树进行一些操作
a.split(v,b);
　　这里需要进行一些解释。join操作的前提是两棵树的key的取值范围不相交，否则会抛出一个异常；合并后平衡二叉树b被清空。split操作中，v是一个与key类型相同的值，表示key小于等于v的元素属于平衡二叉树a，其余的属于平衡二叉树b，注意此时后者已经存有的元素将被清空。

rope

#include<ext/rope>
using namespace __gnu_cxx;


append()
string &append(const string &s,int pos,int n);

//把字符串s中从pos开始的n个字符连接到当前字符串的结尾或

a.append(b);


substr()
s.substr(0,5);
//获得字符串s中从第零位开始长度为5的字符串（默认时长度为刚好开始位置到结尾）


push_back(x);//在末尾添加x
insert(pos,x);//在pos插入x，自然支持整个char数组的一次插入
erase(pos,x);//从pos开始删除x个
copy(pos,len,x);//从pos开始到pos+len为止用x代替
replace(pos,x);//从pos开始换成x
substr(pos,x);//提取pos开始x个
at(x)/[x];//访问第x个元素

支持用数组下标访问，不需要使用迭代器（迭代器会超时）

技巧：有时翻转操作可以维护一个反方向的rope

声明
rope<char> str;

哈希表

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
usingnamespace __gnu_pbds;

cc_hash_table<string,int>mp1;//拉链法
gp_hash_table<string,int>mp2;//查探法(快一些)

不使用C++11的时候比map的效率大大提高