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 =  + ;

int price, menu[MAXN], cnt[MAXN];

template<class T>inline bool nextInt(T &n) {

    T x = , tmp = ;

    char c = getchar();

    while((c < '' || c > '') && c != '-' && c != EOF)

        c = getchar();

    if(c == EOF)

        return false;

    if(c == '-')

        c = getchar(), tmp = -;

    while(c >= '' && c <= '')

        x *= , x += (c - ''), c = getchar();

    n = x*tmp;

    return true;

}

template<class T>inline void Out(T n) {

    if(n < ) {

        putchar('-');

        n = -n;

    }

    int len = , data[];

    while(n) {

        data[len++] = n%;

        n /= ;

    }

    if(!len)

        data[len++] = ;

    while(len--)

        putchar(data[len]+);

}

struct Splay_Tree {

    struct Node {

        int father, childs[], key, cnt, _size;

        inline void init() {

            father = childs[] = childs[] = key = cnt = _size = ;

        }        inline void init(int father, int lchild, int rchild, int key, int cnt, int sz) {

            this -> father = father, childs[] = lchild, childs[] = rchild;

            this -> key = key, this -> cnt = cnt, _size = sz;

        }

    } tre[MAXN];

    int sign, root;

    inline void init() {

        sign = root = ;

    }

    inline bool judge(int x) {

        return tre[ tre[x].father ].childs[] == x;

    }

    inline void update(int x) {

        if(x) {

            tre[x]._size = tre[x].cnt;

            if(tre[x].childs[]) {

                tre[x]._size += tre[ tre[x].childs[] ]._size;

            }

            if(tre[x].childs[]) {

                tre[x]._size += tre[ tre[x].childs[] ]._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 == ) { ///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 == ) {

                tre[++sign].init(, , , x, , );

                root = sign;

                return ;

            }

            int now = root, father = ;

            while() {

                if(tre[now].key == x) {

                    tre[now].cnt ++;

                    update(now), update(father);

                    splay(now, );

                    break;

                }

                father = now;

                if(x > tre[now].key) {

                    now = tre[now].childs[];

                } else {

                    now = tre[now].childs[];

                }

                if(now == ) {

                    tre[++sign].init(father, , , x, , );

                    if(x > tre[father].key) {

                        tre[father].childs[] = sign;

                    } else {

                        tre[father].childs[] = sign;

                    }

                    update(father);

                    splay(sign, );

                    break;

                }

            }

        }

        inline int pre() {

            int now = tre[root].childs[];

            while(tre[now].childs[]) {

                now = tre[now].childs[];

            }

            return now;

        }

        inline int next() {

            int now = tre[root].childs[];

            while(tre[now].childs[]) {

                now = tre[now].childs[];

            }

            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() {

                    if(tre[now].childs[] && x <= tre[ tre[now].childs[] ]._size ) {

                        now = tre[now].childs[];

                    } else {

                        int rchild = tre[now].childs[], sum = tre[now].cnt;

                        if(rchild) {

                            sum += tre[rchild]._size;

                        }

                        if(x <= sum) {

                            int ans = tre[now].key;

                            splay(now, );

                            return ans;

                        }

                        x -= sum;

                        now = tre[now].childs[];

                    }

                }

            }

            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 > ) {

                        tre[root].cnt --;

                        update(root);

                        return ;

                    }

                    if(!tre[root].childs[] && !tre[root].childs[]) {

                        tre[root].init();

                        root = ;

                        return ;

                    }

                    if(!tre[root].childs[]) {

                        int old_root = root;

                        root = tre[root].childs[], tre[root].father = , tre[old_root].init();

                        return ;

                    }

                    if(!tre[root].childs[]) {

                        int old_root = root;

                        root = tre[root].childs[], tre[root].father = , tre[old_root].init();

                        return ;

                    }

                    int pre_node = pre(), old_root = root;

                    splay(pre_node, );

                    tre[root].childs[] = tre[old_root].childs[];

                    tre[ tre[old_root].childs[] ].father = root;

                    tre[old_root].init();

                    update(root);

                }

                inline bool find(int x) {

                    int now = root;

                    while() {

                        if(now == ) {

                            return ;

                        }

                        if(x == tre[now].key) {

                            splay(now, );

                            return ;

                        }

                        if(x > tre[now].key) {

                            now = tre[now].childs[];

                        } else {

                            now = tre[now].childs[];

                        }

                    }

                }

            }

            tre;

            int n, opt, x;

            int main() {

                scanf("%d", &price);

                int id = ;

                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.\n", res);            }        }    }

                    return ;

                }

平衡树
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(,);

//获得字符串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的效率大大提高

巴特西

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

pb_ds

rope

哈希表

最新文章

热门文章