在BZOJ乱逛又发现好东西了

有个冬令营的PPT:C++的pb_ds库在OI中的应用

STL中有一个很神的库。。

#include <ext/pb_ds/xxx.hpp>即可使用 最重要的是NOI系列比赛可以使用!

全称Policy-Based Data Structures(基于策略的数据结构?)

封装了很多很难写的数据结构:各种平衡树、堆、哈希表

并且每一种都比std::的快

一个一个讲吧:

1.堆

支持5种堆:二叉堆、二项堆、rc_二项堆(不知道是什么)、配对堆(可并!可并!)、thin heap(也是Tarjan发明的一个不明所以的堆)

即可声明一个堆

其中pairing_heap_tag可以换成binary_heap_tag、binomial_heap_tag、binomial_heap_tag、thin_heap_tag

操作和std::priority_queue差不多:支持size(),empty(),push(const T),top(),pop(),clear(),另支持begin()和end()遍历,modify(point iterator, const reference),erase(point iterator)

还有一个最爽的join(priority queue &other):将other合并到*this并清空other

据测,在只有push pop join操作时二叉堆较快

在有modify时配对堆较快

当然合并的话应该还是配对堆最爽吧(雾)

2.平衡树

和std::map也是差不多的;如果想用set直接把T定为null_type

支持begin(),end(),size(),empty(),clear(),find(const Key),lower bound(const Key),upper bound(const Key),erase(iterator),erase(const Key),insert(const pair<Key, T>),operator[](const Key),另外支持join(tree &other):和堆的差不多,split(const key reference r key, tree &other):清空other,再将*this中所有大于r_key的元素移入other

在四个参数Key, T, Cmp_Fn, Tag中,前三个都很熟悉了;Tag可以选择rb_tree_tag、splay_tree_tag、ov_tree_tag

但其实还可以再加一个参数:tree_order_statistics_node_update

加了这个之后,就可以使用find_by_order查找第k大元素(以0开始)和order_of_key查找比k小的数的个数

这样大部分功能就都有了

还有个重头戏:自定义update函数

大概就是这么个格式,我反正也不会==大概就是蒯

3.hash表

cc和gp任选其一,支持find和[],比map和unordered_map都快得多

说点什么

您将是第一位评论人!

提醒
wpDiscuz